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.
Watch video NFA to Regular Expression Conversion, and Example online without registration, duration hours minute second in high quality. This video was added by user Easy Theory 09 March 2020, don't forget to share it with your friends and acquaintances, it has been viewed on our site 101,20 once and liked it 2.7 thousand people.