Conversion of NFA to DFA (Powerset/Subset Construction Example)
Vložit
- čas přidán 10. 07. 2024
- 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 • What is an Nondetermin... 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
If you like this content, please consider subscribing to my channel: / @easytheory
▶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.
Next video! Proving that {0^n 1^n : n at least 0} is not regular: czcams.com/video/5GG8goBW9gw/video.html
*You are god.*
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.
Thank you so much man. You're way more competent than my university professor.
Blenderfier you're welcome!
🤣🤣🤣🤣
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.
it's the same thing though, just with the table you keep track of everything. With a larger alphabet it could get messy.
A lot of videos didn't include the empty string Epsilon. This helps a lot!
my lecture notes look like alien language but this thing right here, anybody could understand this. Thank you so much
Really took all the complex mind bending gymnastics out of it thank you.
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!
keep up the good work
This is a the best explanation anyone can get on this course
Thank you SO MUCH for your explanation, I got this concept literally just now!! Thanks a lot!
Thanks! You did a great job explaining it!
I’m glad i came across this channel cuz my teacher sucks
Super helpful for my discrete 2 exam this week! Thanks so much :D
Ok this seemed so difficult in class, but you made it easy. Thank you!!
Holy crap this method is so beautiful! Thanks!!!
Your videos are so helpful, thank you!
You're welcome!
Wow! Congrats on the clear explaination
Amazing job, you make solving these problems much easier.
Glad to help
This was very easy to follow. Thanks a lot :)
You're very welcome!
this is some good stuff bro
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.
Great explanation , thanks
Thank you a lot, great work!
Thanks a bunch! Super clear!
Thanks a lot, I finally got it
very good video, love it
Great content!
Great video!
Thank you , i understood really well !
Thanks for this great video
Nice explanation, thanks
LITERALLY PERFEECT VIDEO
Legendary video
needed this
best teacher evaaah
thanks a lot! u just saved my mid
Thanks, along side this. Wikipedia helped me grasp the theoretical side a little aswell
way better than my professor!
C'est incroyable!
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.
I'm always watching your video! And it is the most awesome lecture I've ever seen since I was born!!!! Thank you SOOOO much!!!!
Thank you!
youre awesome. thanks
you the best.
Thanks man.
really late to this gem but thank you! I have a question what if there was also an epsilon from q1 to q3 and an epsilon from q3 to q2 what would the starting state look like in the DFA?
Thanks a lot! : D
very clear
Thx dude!
thank you so much
What do you do if you have a lamda transition?
I don't get the echelon part of determining the set of states.
At 3:11 shouldnt it be just q1 instead of just q2, since getting a 'b' wont let us transition out of that state?
I'm not sure where you're getting q1. Note that the state we are testing "from" is {q0, q1} - note that q0 does not have a "b" transition, and q1 does have one to q2. So the resulting "state" is {q2}.
But what if theres no epsilon enclosure in the NFA? How do I start? Do I just have to start with a if f.e q0 points with a to q1?
yes
Can someone explain to me how {q1, q3} + a = {q1, q2} ?? Thats the only thing I cant understand. Is it because theres no defined states from q3 for the input 'a' this 'thread' kinda 'dies' and we can ignore it completely while q1 when given 'a' can result with both q1 and q2 and thats how we compe up with that?
from q1 through 'a' we can go to states {q1,q2}. from q2 we cant go to any state using 'a' transition. So next, when we consider the epsilon closures of q1 and q2, i.e. which states we can go to using epsilon transitions, it is themselves ; {q1,q2}. Hope that helps!
What if I don't have Epsilon on my NFA?
3:54 "The set of states I could be in from q_2 reading an 'a' is q_0, q_1, q_2" Could you please explain me why "q_1" too? Starting from q_2, with an epsilon we can't go anywhere, with an a we can only go in q_0 and q_2 itself, and with a b only in q_3. Where am I wrong? Thanks in advance.
From q_2 on input 'a' you can go to q0 and to the epsilon closure of q0 which is q1
intro is iconic lol 🤣🤣
"Just use a computer to do this, don't do it by hand".
Meanwhile I'm over here studying for my thermotical foundations exam where I know that this will show up.
*heart react
Can you eventually tell me which book(s) your videos rely on? Because the professor in our Theoretical Computer Science lecture is not explaining everything thoroughly and deeply. Thanks in advance.
It's mainly the Sipser textbook, 3rd edition. All the notation I use is from there too.
How is this a DFA? {q1,q3} have 2 inputs leading to the same state {q1,q2}. This makes it non-deterministic.
Not quite. Non-determinism happens when you have 2 transitions *with the same symbol* going from the same state. In this case, it's 2 transitions with *different* symbols. Only one of the two can possibly be taken at a time.
abi çok tatlısın da anlatırken niye sinirleniyorsun anlamadım
Ahhhhh why are you making me do it by hand Sir! 😡
Man, I'm afraid you have a video in your ads...
Don't understand for shit, plez make second vid...