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.

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    • What is an Nondeterministic Finite Au...   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

If you like this content, please consider subscribing to my channel:    / @easytheory  

▶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◀
[email protected]

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