NFA to Regular Expression Conversion, and Example

Here we convert a simple NFA into a regular expression as easily as possible. We first modify the NFA so that there is a single start state with nothing going into it, and a single final state with nothing leaving it. Then we "rip" states out one at a time until we have just two states left, which contains the desired regular expression.
This is known as the "GNFA" (Generalized NFA) method.

Timestamps:
0:00 - Intro
0:39 - Overview of Steps
1:17 - Fix the NFA
2:10 - Start of Ripping States
2:39 - Rip q3
6:30 - Rip q2
9:10 - Rip q0
11:25 - Rip q1
13:05 - Conclusion

▶ADDITIONAL QUESTIONS◀
1. Does the GNFA method truly work for ANY NFA?
2. What happens if we ripped the states out in a different order?

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

[EasyTheory]

Thanks to my supporters Yuri, vinetor, Ali (Youtube) and Bruno, Timmy, Micah (Patreon) for making this video possible! If you want to contribute, links are in the video description.

[alisonlee]

Wish textbooks had more examples because they help a lot more compared to just text and theorems. Thanks so much!

[kalastasgamingshack]

I have a test tomorrow and didn't understand anything from my Lecturer . This video is a gold mine. Thank you!!!

[laurenlin]

Thank you so much for this easy to follow explanation! Was so confused by my professor but you're a life saver

[davidlancaster]

College professor spent 2 hours explaining this. Watched this video on double speed in 7 minutes.

[michaeltaylor]

Dude... I love you. The in and out list made this so easy. My college professor was just having us send it and I couldn't get it, you legitimately just saved me for my mid term. I wish you were my professor, thank you!

[Computerix]

Didn't understand anything from my professor's book, watched this and understood everything thanks !

[kavinanand]

This is a fantastic explanation. The In/Out decomposition really helped!

[ThangNguyen-koze]

I have an exam tomorrow and this just saved my life. Thank you for making my Computer Science life a bit easier.

[SatvikAryabcs]

Thank u sir from INDIA, there r very few utubers who have covered this topic but from all those, ur explanation is outstanding.

[aadarshrajesh]

searched entire youtube for such an example, thankyou so much 👍😁

[luissuarez]

I was reading the textbook like crazy and could not understand it at all but your video allowed me to grasp this much better . Thank you so much!!

[cagla]

Thank you soooo so much!! I didn't understand what my professor was doing in the lecture because he didn't explain what he did and why he did it. You saved me !

[hashimmahmood]

hands down the best tutorial on FA to RE conversion using GNFAs

[ayushsharma]

Hats off, tried 10+ resource and now this is the only video i will refer in future as well for NFA->RE. The Best, thanks

[mehrdadkiani]

Finally, I found a clear explanation for these kinds of questions, thank you.

[ahmedbadre]

اقسم بالله فنان اول مره افهم التحويل بالسهولة دي ❤❤❤ Thanks. Your explanation is amazing

[CoolEngineering-nmmi]

I have a midterm tomorrow and this video literally are saving me!! thank you

[bettyteng]

Thank you so much. This is the easiest one to understand among all the other videos about this.

[ClaudioBOsorio]

Incredible. You are a great professor. I like it when you put it into steps. It is really easy theory. I think the biggest challenge is just explaining it and you do a very good job at it.