Conversion of NFA to DFA (Powerset/Subset Construction Example)

Here we convert a simple NFA with four states into an equivalent DFA. We first compute the epsilon-closure of the start state, and then make that the start state of the DFA. Then we "build states as needed" until we "complete" the DFA (i.e., every transition needed is present). And lastly, the final states of the DFA are the ones where the set of states contains a final state from the NFA. In our example, we ended up generating 9 states out of the possible 16.

I also give advice on how to easily convert any NFA into an equivalent DFA, and what steps are needed at each point. Note that the process does not require intuition, but rather computing which states should be included.

What is a nondeterministic finite automaton (NFA)? It is a finite state machine, with "states" and transitions between them, allowing choices as compared to a deterministic FA. See https://www.youtube.com/watch?v=P5iWwYtwlwg&ab_channel=EasyTheory for more details.

Timestamps: 0:00 - Intro 0:12 - Guidelines 0:47 - Epsilon closure of {q0} 1:45 - Transitions for {q0} 3:14 - Transitions for {q2} 4:25 - Transitions for {q3} + "dead" state 5:19 - Transitions for {q1} 6:05 - Transitions for {q1,q2} 7:21 - Transitions for {q2,q3} 7:50 - Transitions for {q1,q3} 9:05 - Transitions for {q0,q1,q2} 10:10 - Final States 11:25 - Conclusion

Patreon: https://www.patreon.com/easytheory

If you like this content, please consider subscribing to my channel: https://www.youtube.com/channel/UC3VY6RTXegnoSD_q446oBdg?sub_confirmation=1

▶ADDITIONAL QUESTIONS◀

1. The DFA we generated had 9 states, where there are 16 possible subsets of 4 states. What happened to the other 7?
2. Can you create an NFA such that the corresponding DFA must have all possible states?
3. Same as Question 2, but where the NFA has no epsilon transitions.

▶SEND ME THEORY QUESTIONS◀ ryan.e.dougherty@icloud.com

▶ABOUT ME◀ I am a professor of Computer Science, and am passionate about CS theory. I have taught over 12 courses at Arizona State University, as well as Colgate University, including several sections of undergraduate theory. ... https://www.youtube.com/watch?v=jMxuL4Xzi_A