NFA to Regular Expression Conversion, and Example - Easy Theory

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.

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 https://www.youtube.com/watch?v=P5iWwYtwlwg&ab_channel=EasyTheory for more details.

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

Easy Theory website: https://www.easytheory.org Become a member: https://www.youtube.com/channel/UC3VY6RTXegnoSD_q446oBdg/join Paypal: https://paypal.me/easytheory Patreon: https://www.patreon.com/easytheory

If you like this content, please consider subscribing to my channel: https://www.youtube.com/channel/UC3VY6RTXegnoSD_q446oBdg?sub_confirmation=1

▶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◀ 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. ... https://www.youtube.com/watch?v=UKYvP8aS7fM