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

Рет қаралды 29,067

Күн бұрын

Пікірлер: 42

@kostastsaousis7445 2 жыл бұрын

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!

@rushilpunya2552 2 жыл бұрын

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

@adityap613 Жыл бұрын

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

@NuggzBii 3 жыл бұрын

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

@skmanoop Жыл бұрын

It is a typo. the self loop on q_2 is for input b instead of a.

@Baraa_ali62 2 жыл бұрын

Thanks , Great job

@jussef2057 2 жыл бұрын

That intro is a banger

@supamdeepbains5172 3 жыл бұрын

Great video!!

@vimalathithand917 10 ай бұрын

Awesome !

@elmerfuddpt2 Ай бұрын

thank you so much !!!!

@volkanulker6432 3 жыл бұрын

So clear

@fpsgod7259 Жыл бұрын

Great video :)

@vincenzoriccardo138 4 ай бұрын

good job fratm

@MLOasis 9 ай бұрын

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

@Lexaugd 4 жыл бұрын

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)?

@EasyTheory 4 жыл бұрын

Thanks! What do you mean by "universe"?

@Lexaugd 4 жыл бұрын

@@EasyTheory start is the state that goes to the accept state(state q0) with the empty string and the Finnish state to which the accept state arrives at with an empty string.

@EasyTheory 4 жыл бұрын

@@Lexaugd Ok then yes that's true. If the original NFA's start state was final, then in the "fixed" NFA there will be an epsilon transition from this state to a *brand new* final state. The reason to do this is that whatever the final state is, it cannot have any transitions "leaving" it.

@Lexaugd 4 жыл бұрын

@@EasyTheory thank you, I really appreciate your response!

@Kbro91 10 күн бұрын

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

@yusufaksoy3693 2 жыл бұрын

Super.💪🤟

@satvikarya569 4 жыл бұрын

In 7:00 why it is not ( b* U ba*a)???

@selinamartinez8067 2 жыл бұрын

It's quite late, but I will answer it for you! In 7:00 , you should write b instead of b*. The reason is because it is still on the self loop transition(which is from qo to qo)! The sign '*' means that you're gonna use it instead of self loop transaction! You can use ( b U ba*a)* instead of ( b U ba*a) when you rip q0. Then now you can use * on the whole thing 'b U ba*a'. But 'b*' instead of 'b' what you said, can't be!

@rohanhaldiya6890 Жыл бұрын

@@selinamartinez8067 Can you explain more?

@siddhantdash4955 4 жыл бұрын

Is there any way to find minimal regex?

@EasyTheory 4 жыл бұрын

Good question! This is actually quite complicated, but there is: first, generate a regex for the corresponding NFA (and convert this NFA into an equivalent DFA D). Then, enumerate all possible regexes that are smaller than the one generated. For each, convert them to an equivalent DFA, and then check if the language of this DFA is the same as D's. Then keep the smallest regex that you found to be equivalent to D. The "interesting" question is whether we can make this algorithm faster. It turns out that, unless P = NP, there is no polynomial-time algorithm to find the smallest regex. In fact, the smallest regex *cannot even be approximated* in polynomial time.

@siddhantdash4955 4 жыл бұрын

@@EasyTheory wow!! Thanks.

@rheabhatia6607 4 жыл бұрын

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

@EasyTheory 4 жыл бұрын

Rhea Bhatia good question! The idea is to put epsilon transitions from all accepting states to a new accepting state, and make all of the other accepting states now non-accepting. Should be easy to prove that it works.