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

[@EasyTheory]

Next video! Proving that {0^n 1^n : n at least 0} is not regular: kzbin.info/www/bejne/a3iqaZqld7xsndk

[@onurcanisler]

*You are god.*

[@aokellermann]

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

[@EasyTheory]

Blenderfier you're welcome!

[@richarddansopeprah17]

🤣🤣🤣🤣

[@hectorg362]

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.

[@wasgehdabman]

it's the same thing though, just with the table you keep track of everything. With a larger alphabet it could get messy.

[@bachi5373]

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

[@hurboglan1003]

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

[@2v2]

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

[@ahmadqureshi5366]

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

[@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.

[@thelogbob281]

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!

[@yitooasrat4668]

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

[@jjLishy]

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

[@dariusztomaszewski-guerrer7874]

awesome video dude - really well explained in a timely manner thanks

[@edgermoreno3945]

Amazing job, you make solving these problems much easier.

[@EasyTheory]

Glad to help

[@creeper-d5v]

Explained much better than my professor. :)

[@laurenshoste2773]

better explained than university professor

[@IncendiaHL]

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

[@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.

[@manalasmouh5549]

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

[@kevalgandhi1272]

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

[@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.

[@saladrockstar]

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

[@reyhanehakhlaghian9523]

Your video helped me a lot. thank you!

[@SimoneBova-k8l]

Wow! Congrats on the clear explaination

[@NguyenTran-sn8vt]

Very easy to understand viddeo. Thank you so much!

[@amesund]

Your videos are so helpful, thank you!

[@EasyTheory]

You're welcome!

[@charlie10010]

Holy crap this method is so beautiful! Thanks!!!

[@abel5545]

This was very easy to follow. Thanks a lot :)

[@EasyTheory]

You're very welcome!

[@aahilrafiq4850]

Thank you , i understood really well !

[@selinamartinez8067]

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!!!!

[@nikolaytodorov2416]

Great stuff, thank you!

[@shanestevens516]

way better than my professor!

[@isam3l3]

Thanks, along side this. Wikipedia helped me grasp the theoretical side a little aswell

[@manalasmouh5549]

best teacher evaaah

[@cameronfrazier8330]

LITERALLY PERFEECT VIDEO

[@Kipp3t]

you are the GOAT!

[@TiaDzn]

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.

[@zeking3844]

From q_2 on input 'a' you can go to q0 and to the epsilon closure of q0 which is q1

[@溫皓宇-u6y]

very good video, love it

[@jiwooahn1966]

thanks a lot! u just saved my mid

[@1SnowBall1]

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?

[@forthehomies7043]

Beautiful!

[@KonstructChannel]

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?

[@victorolaru8488]

yes

[@ahmetmurtezaoglu]

Thank you a lot, great work!

[@nyanyacalc]

Nice explanation, thanks

[@dionysismaniatakosmusic]

Thanks! You did a great job explaining it!

[@britannio]

Legendary video

[@memoymishra4619]

C'est incroyable!

[@Leaf682]

At 3:11 shouldnt it be just q1 instead of just q2, since getting a 'b' wont let us transition out of that state?

[@EasyTheory]

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

[@enisozer5007]

Great content!

[@john_is_never_home6871]

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

[@kenana3456]

Great explanation , thanks

[@TotallyOKaYProductions]

this is some good stuff bro

[@glizzy5154]

needed this

[@booqueefiusbartholomuleiii9957]

Thanks for this great video

[@mohammedmansour3567]

What do you do if you have a lamda transition?

[@dewman7477]

I don't get the echelon part of determining the set of states.

[@wujekjerry1188]

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?

[@ChamaliVishmani1999]

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!

[@anarmehraliyev1286]

Thanks a lot, I finally got it

[@stevehof]

Thanks a bunch! Super clear!

[@javawithhawa]

Great video!

[@munteanionut3993]

What if I don't have Epsilon on my NFA?

[@zacklnwza0073]

you the best.

[@Mike-kq5yc]

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.

[@EasyTheory]

It's mainly the Sipser textbook, 3rd edition. All the notation I use is from there too.

[@wentaohe3076]

very clear

[@azuboof]

youre awesome. thanks

[@hlo6217]

intro is iconic lol 🤣🤣

[@andreymarchuk8938]

Thank you!

[@gurkengerd9981]

How is this a DFA? {q1,q3} have 2 inputs leading to the same state {q1,q2}. This makes it non-deterministic.

[@EasyTheory]

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.

[@adityamishra6389]

Thanks man.

[@ahmetkarakartal9563]

thank you so much

[@thelockenbubi7117]

Thx dude!

[@gioscopantana8349]

thatnks!

[@munteanionut3993]

Thanks a lot! : D

[@caominhnhat1455]

*heart react

[@MatthewMiller-b5e]

Taylor Matthew Williams Helen Martinez Jason

[@MatthewMiller-b5e]

Perez Edward Hall Brenda Jones Laura

[@itsweird3373]

abi çok tatlısın da anlatırken niye sinirleniyorsun anlamadım

[@ion_propulsion7779]

Ahhhhh why are you making me do it by hand Sir! 😡

[@sharpvik]

Man, I'm afraid you have a video in your ads...

[@Tf_vincent]

Don't understand for shit, plez make second vid...

[@VonSteiner1]

I hate professors for being so damn stupid. Why not just teach it this way?

[@armandduval4893]

Great video, thanks a lot!