NFA to Regex Conversion Example #1, 'Simple' (GNFA Method)

Показать описание

▶ABOUT ME◀
I am a professor of Computer Science, and am passionate about CS theory. I have taught many courses at several different universities, including several sections of undergraduate and graduate theory-level classes.

Рекомендации по теме

Комментарии

After having to search for hours to find a clear and simple explanation of NFA to regex with state eliminaiton, your video clearly beats everything else! Thank you very much and continue your amazing job!

kostastsaousis

Dude you are an absolute beast. Thanks so much for helping me get through CSE 355

rushilpunya

Amazing video, understood how to do the conversion in 5 minutes.

adityap

In your example around the 2 minute mark, you claim the automaton is a DFA. That is incorrect, because in a DFA, a state can never transition on two of the same symbol. I.e., q_2, cannot self loop, and transition to q_0 on the same input. That implies the automaton has guessing power, which is a prime characteristic of an NFA

NuggzBii

What if the original initial state was also a final state?

Kbro

I love your videos!
I'd also like to ask a question:
If the start state is also an accepting state and there is no more accepting states, do we draw an arrow from the universe to this start/accept state and back to the universe (Start/Finnish states)?

Lexaugd

Shouldn't it be (b U (b a*)*) since we can loop as many times as we wish over q0 after removing q2 ?

MLOasis

Is there any way to find minimal regex?

siddhantdash

Sir why did you put whole * in last step (rip q0) but why no * for a in Rio q1

ezhilvathani

How do you find regex given an nfa with multiple accepting states?

rheabhatia

I ripped q1 first and got a shorter, different result: (b∪ba*a)*a is it wrong?

bloodthirstybutcher

Hello, can anyone tell me how i can write regex for the trap states ??? Do i just omit them and not take them into account ?

barisonearth

NFA to Regex Conversion Example #1, 'Simple' (GNFA Method)

NFA to Regular Expression Conversion

NFA to Regular Expression Conversion, and Example

NFA to Regex Conversion Example #1, 'Simple' (GNFA Method)

NFA to Regex Conversion Example #2, 'More Complicated' (GNFA Method)

28 finite automata to regular expression

Conversion of NFA to Regex PROOF (GNFA Method)

Regex to NFA Conversion Isn't Hard! (Sipser 1.28a)

DFA to Regular Expression Conversion

Conversion of NFA to Regular Expression using Arden's Theorem by Bharathi Patnala

1 - Arden's Theorem Example: Converting NFA to Regular Expression | Theory of Computation

A Double Conversion: Regular Grammar to NFA to Regex!

Regular Expression (Regex) to NFA Example Conversion

2 - Arden's Theorem Example: Converting NFA to Regular Expression | Theory of Computation

Conversion of Finite Automata to Regular Expression using Arden's Method || TOC || FLAT

Conversion of Regular Expression to Finite Automata - Examples (Part 1)

5.3 DFA to GNFA to Regular Expression

NFA To DFA Conversion Using Epsilon Closure

Solve the (a/b)*aa(a/b)* regular expression into NFA using Thompson construction

Conversion of Regular Expression to Finite Automata - Examples (Part 2)

The 'General' General NFA Method (NFA to Regex, GNFA)

DFA to Regular Expression Conversion (when the DFA has Multiple Final States)

Regular Expression (Regex) to NFA Conversion

Conversion of Regular Expression to Finite Automata - Examples (Part 3)

Regular Expression to NFA

Solve the (a/b)aa(a/b) regular expression into NFA using Thompson construction