DFA Minimization Algorithm + Example

Here we consider the problem of minimizing the number of states in a deterministic finite automaton (DFA). The key here is to identify pairs of states that are "distinguishable", in the sense that reading any string from both of them eventually will lead to an accept state in one case, and a non-accept state in the other case. Then we build the definition of distinguishable states recursively. We conclude with two examples of DFAs: one where no states can be removed, and another where multiple states can be removed.
Timeline:
0:00 - Intro
0:30 - Goals of the Video
1:04 - Distinguishing States Example
4:07 - Distinguishing Strings Example
7:17 - Distinguishing States Definition
9:40 - DFA Minimization Example 1
15:35 - DFA Minimization Example 2
20:18 - Conclusion
Thanks to the following supporters of the channel for helping support this video. If you want to contribute, links are below.
Dolev Abuhazira, Josh Hibschman, Micah Wood, Morgan Jones, Patrik Keinonen, Simone Glinz, Tao Su, Timothy Gorden, unit220, Valentine Eben
Easy Theory Website: www.easytheory.org
Become a member: / @easytheory
Donation (appears on streams): streamlabs.com/easytheory1/tip
Paypal: paypal.me/easytheory
Patreon: / easytheory
Discord: / discord
Merch:
Language Hierarchy Apparel: teespring.com/language-hierar...
Pumping Lemma Apparel: teespring.com/pumping-lemma-f...
If you like this content, please consider subscribing to my channel: / @easytheory
▶SEND ME THEORY QUESTIONS◀
[e-mail]
▶ABOUT ME◀
I am a professor of Computer Science, and am passionate about CS theory. I have taught many courses at several different universities, including several sections of undergraduate and graduate theory-level classes.

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

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

[@gelid451]

Extremely helpful video. Thanks for making it.

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

[@qqqqqqqqqqqqqqq67]

Best CS channel on youtube.

[@Edigor100]

saved my homework assignment, thanks man

[@bangvu2127]

Thanks for the great explanation

[@CipriValdezate]

Excelent and very helpful explanation, thank you very much.

[@HeisenbergHK]

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

[@stijnjongbloed1]

Thanks for the video!

[@saeedbarari2207]

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

[@yerdauletseidizhappar8605]

You are a lifesaver

[@awsafrafin1467]

Thank you sir. It was easy.

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

[@AshutoshGera]

Great video, thanks :)

[@vimalathithand917]

Amazing!

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

[@keivansf3459]

Thanks a lot

[@exponentialf]

🔥

[@Apocalymon]

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

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

[@peterle4672]

This is the Myhill Nerode theorem

[@user-yb5cn3np5q]

So what is the complexity of this algorithm? If you don't care, twice inverting arrows in DFA and converting resulting DFA to NFA gives you Brzozowski's algorithm. It can be implemented and explained in 5 minutes, the only catch is that it's running in exponential time. But if it doesn't only look like the video was supposed to describe efficient Hopcroft's algorithm, it failed.