DFA Minimization Algorithm + Example

[@qqqqqqqqqqqqqqq67]

Best CS channel on youtube.

[@trabajosdeclase9299]

this is really well explained. i cant thank enough

[@gold4963]

12:10. Checking 1 and 2 a transition.
12:39. Checking 1 and 2 b transition.
13:00. Checking 1 and 4 a transition.
13:12. Checking 1 and 4 b transition.
13:28. Checking 2 and 4 a transition.
13:40. Checking 2 and 4 b transition.
14:10. Checking 1 and 6 a transition.
14:18. Checking 1 and 6 b transition.
14:28. Checking 2 and 6 a transition.
14:34. Checking 2 and 6 b transition.
14:43. Checking 4 and 6 a transition.
14:49. Checking 4 and 6 b transition.
14:58. Going through chart again, checking all empty spaces.
15:04. Checking 2 and 4 a transition.
15:09. Checking 2 and 4 b transition.
15:18. Checking 4 and 6 a transition.
Checking 4 and 6 b transition is unnecessary; the a transition is already marked as distinguishable.
Algorithm is now complete, and it turns out this is the minimized DFA anyways. XD

[@HeisenbergHK]

I have a very important quiz in just one hour
Thanks for this video

[@QmiStudying]

My teacher didn't really explain why the equivalent states work, I had a slight grasp of why the algorithm works but it never clicks. Thanks to this explation I can fully understand it, thank you sir

[@Edigor100]

saved my homework assignment, thanks man

[@destructicon844]

15:15, how come 2 and 4 are distinguished, they go to the same state on an a transition, and accepting on b?

[@destructicon844]

Oh because the accepting states are distinguished

[@gelid451]

Extremely helpful video. Thanks for making it.

[@gold4963]

Thanks so much for this video! I was able to trace through the example and figure out how to the use the algorithm and the distinction table!

[@saeedbarari2207]

this would be whole lot easier if scientists back then didn't call "distinguishable"s "not indistinguishable"...

[@lowerbound4803]

18:50 Why couldn't array[3, 5] be marked during the process?

[@scotthoward8308]

This took me a while too - 3 and 5 are defined as final states when he made the state machine (he just didn't say it out loud). They are indicated by the double circle symbols.

[@CipriValdezate]

Excelent and very helpful explanation, thank you very much.

[@awsafrafin1467]

Thank you sir. It was easy.

[@nekozza]

very helpful man thanks!

[@bangvu2127]

Thanks for the great explanation

[@RickeyBowers]

The state merging step, using the complete lower triangular matrix involves finding cycles? Thank you /so/much/ for working through these examples! You sir, are going to have a large audience in time. I'm going to try working through some larger examples to discover the groupings needed at the end.

[@bigguccitaurus1395]

thanks for saving my life. i found it very difficult to motivate myself to get to know this subject, as it is quite theoretical and seems quite useless at first.

[@stijnjongbloed1]

Thanks for the video!

[@yerdauletseidizhappar8605]

You are a lifesaver

[@Apocalymon]

What does this have to do with the minimum circuit size problem?

[@vimalathithand917]

Amazing!

[@AshutoshGera]

Great video, thanks :)

[@exponentialf]

🔥

[@keivansf3459]

Thanks a lot

[@peterle4672]

This is the Myhill Nerode theorem