How does the DFA/NFA to Regular Expression work? (GNFA Conversion) - 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.
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
Facebook: https://www.facebook.com/easytheory/
Twitter: https://twitter.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.
▶ABOUT THIS CHANNEL◀
The theory of computation is perhaps the fundamental
theory of computer science. It sets out to define, mathematically, what
exactly computation is, what is feasible to solve using a computer,
and also what is not possible to solve using a computer.
The main objective is to define a computer mathematically, without the
reliance on real-world computers, hardware or software, or the plethora
of programming languages we have in use today. The notion of a Turing
machine serves this purpose and defines what we believe is the crux of
all computable functions.
This channel is also about weaker forms of computation, concentrating on
two classes: regular languages and context-free languages. These two
models help understand what we can do with restricted
means of computation, and offer a rich theory using which you can
hone your mathematical skills in reasoning with simple machines and
the languages they define.
However, they are not simply there as a weak form of computation--the most attractive aspect of them is that problems formulated on them
are tractable, i.e. we can build efficient algorithms to reason
with objects such as finite automata, context-free grammars and
pushdown automata. For example, we can model a piece of hardware (a circuit)
as a finite-state system and solve whether the circuit satisfies a property
(like whether it performs addition of 16-bit registers correctly).
We can model the syntax of a programming language using a grammar, and
build algorithms that check if a string parses according to this grammar.
On the other hand, most problems that ask properties about Turing machines
are undecidable.
This Youtube channel will help you see and prove that several tasks involving Turing machines are unsolvable---i.e., no computer, no software, can solve it. For example,
you will see that there is no software that can check whether a
C program will halt on a particular input. To prove something is possible is, of course, challenging.
But to show something is impossible is rare in computer
science, and very humbling.
Видео How does the DFA/NFA to Regular Expression work? (GNFA Conversion) - Easy Theory канала Easy Theory
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
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
Facebook: https://www.facebook.com/easytheory/
Twitter: https://twitter.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.
▶ABOUT THIS CHANNEL◀
The theory of computation is perhaps the fundamental
theory of computer science. It sets out to define, mathematically, what
exactly computation is, what is feasible to solve using a computer,
and also what is not possible to solve using a computer.
The main objective is to define a computer mathematically, without the
reliance on real-world computers, hardware or software, or the plethora
of programming languages we have in use today. The notion of a Turing
machine serves this purpose and defines what we believe is the crux of
all computable functions.
This channel is also about weaker forms of computation, concentrating on
two classes: regular languages and context-free languages. These two
models help understand what we can do with restricted
means of computation, and offer a rich theory using which you can
hone your mathematical skills in reasoning with simple machines and
the languages they define.
However, they are not simply there as a weak form of computation--the most attractive aspect of them is that problems formulated on them
are tractable, i.e. we can build efficient algorithms to reason
with objects such as finite automata, context-free grammars and
pushdown automata. For example, we can model a piece of hardware (a circuit)
as a finite-state system and solve whether the circuit satisfies a property
(like whether it performs addition of 16-bit registers correctly).
We can model the syntax of a programming language using a grammar, and
build algorithms that check if a string parses according to this grammar.
On the other hand, most problems that ask properties about Turing machines
are undecidable.
This Youtube channel will help you see and prove that several tasks involving Turing machines are unsolvable---i.e., no computer, no software, can solve it. For example,
you will see that there is no software that can check whether a
C program will halt on a particular input. To prove something is possible is, of course, challenging.
But to show something is impossible is rare in computer
science, and very humbling.
Видео How does the DFA/NFA to Regular Expression work? (GNFA Conversion) - Easy Theory канала Easy Theory
Показать
Комментарии отсутствуют
Информация о видео
Другие видео канала
![Theory of Computation #53: NFA to Regex Conversion Example #1, "Simple" (3-State DFA, GNFA Method)](https://i.ytimg.com/vi/nCsY0LBuE_4/default.jpg)
![Theory of Computation #28: How do you convert an NFA to DFA? (Example, Powerset/Subset Construction)](https://i.ytimg.com/vi/jMxuL4Xzi_A/default.jpg)
![Regular Expressions - Computerphile](https://i.ytimg.com/vi/528Jc3q86F8/default.jpg)
![Regular Languages & Finite Automata (Solved Problem 1)](https://i.ytimg.com/vi/_dfj__KOo8U/default.jpg)
![](https://i.ytimg.com/vi/FNyifywALTA/default.jpg)
![Theory of Computation #78: What is a Context-Free Grammar (CFG)? Context-Free Language (CFL)?](https://i.ytimg.com/vi/h1OSmLSacNA/default.jpg)
![NFA to Regular Expression Conversion](https://i.ytimg.com/vi/OKFrju0HB7k/default.jpg)
![Theory of Computation #63: Pumping Lemma FOUR Examples and proof Strategies (Regular Languages)!](https://i.ytimg.com/vi/I3FuVKVgLCA/default.jpg)
![Deterministic Finite Automata (Example 1)](https://i.ytimg.com/vi/40i4PKpM0cI/default.jpg)
![Pushdown Automata (Formal Definition)](https://i.ytimg.com/vi/JtRyd7Svlew/default.jpg)
![DFA to Regular Expression Conversion (when the DFA has Multiple Final States)](https://i.ytimg.com/vi/fRVljh8y7Qw/default.jpg)
![Regular Expression to NFA](https://i.ytimg.com/vi/RYNN-tb9WxI/default.jpg)
![Convert NFA to DFA](https://i.ytimg.com/vi/taClnxU-nao/default.jpg)
![Regular Expression](https://i.ytimg.com/vi/upu_TeZImN0/default.jpg)
![Regular Languages in 4 Hours (DFA, NFA, Regex, Pumping Lemma, all conversions) - Easy Theory](https://i.ytimg.com/vi/bK8LVFWA0L8/default.jpg)
![Theory of Computation #89: Context-Free Grammar to Pushdown Automaton (CFG to PDA Conversion)](https://i.ytimg.com/vi/ZImtQBMSW_Y/default.jpg)
![From NFAs to Regular Expressions by State Elimination (Idea)](https://i.ytimg.com/vi/4tFXe74xMEM/default.jpg)
![Conversion of NFA to DFA (Example 2)](https://i.ytimg.com/vi/i-fk9o46oVY/default.jpg)
![Theory of Computation #10: How to make a VERY EASY DFA for a*b*c* - Easy Theory](https://i.ytimg.com/vi/0P82hNNbQOA/default.jpg)
![Theory Of Computation Lecture 63--Conversion of Finite automata to Regular Expression and vice versa](https://i.ytimg.com/vi/dBwx2PVicTY/default.jpg)