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.

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

▶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◀

▶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.

[aokellermann]

Thank you so much man. You're way more competent than my university professor.

[hectorg]

I personally like this version better than the version where you are building a table of transition states and then drawing out the DFA with that table.

[bachi]

A lot of videos didn't include the empty string Epsilon. This helps a lot!

[laurenshoste]

better explained than university professor

[creeper-dv]

Explained much better than my professor. :)

[ahmadqureshi]

Never thought I would be learning theoretical Informatics from Dexter. WOW!!!

[hurboglan]

my lecture notes look like alien language but this thing right here, anybody could understand this. Thank you so much

[jjLishy]

WOW?!?!?! I THOUGHT THE LAST VIDEO I SAW WAS THE BEST BUT URS EVEN BETTER!!!!

[v]

Really took all the complex mind bending gymnastics out of it thank you.

[JayashreeAPElumalai]

Thank you soo much. Had to study this for finals and I was confused by my own notes. After many vids yours was the only one that answered all my confusions.

[breakloop]

i get uni's might have to stick with teaching the most 'formal/textbook' ways of solving a problem. but being taught these hacky but intuitive methods would make overall comprehension such a breeze and personally i think that's what education should be about.

[thelogbob]

incredible, incredible video! thank you so much for doing what my textbook could not which would be explaining this process in a simple yet explanatory manner. Have a great day!

[manalasmouh]

I’m glad i came across this channel cuz my teacher sucks

[yitooasrat]

keep up the good work
This is a the best explanation anyone can get on this course

[edgermoreno]

Amazing job, you make solving these problems much easier.

[IncendiaHL]

Ok this seemed so difficult in class, but you made it easy. Thank you!!

[saladrockstar]

Super helpful for my discrete 2 exam this week! Thanks so much :D

[helcomn]

Thanks! In the end i was left with only one final state and it was the one that i started with. I checked my DFA and there was no route starting from my ε-enclosure and getting back there, so I assumed it was alright. I'd be happy to hear from your side to see if i did anything questionable.

P.S i didnt go to my uni class but you seem superior.

[kevalgandhi]

Thank you SO MUCH for your explanation, I got this concept literally just now!! Thanks a lot!

[SimoneBova-kl]

Wow! Congrats on the clear explaination