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!
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
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!
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 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.
@@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.
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.
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.
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!
Dude you are an absolute beast. Thanks so much for helping me get through CSE 355
Amazing video, understood how to do the conversion in 5 minutes.
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
It is a typo. the self loop on q_2 is for input b instead of a.
good job fratm
That intro is a banger
Thanks , Great job
In 7:00 why it is not ( b* U ba*a)???
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!
@@selinamartinez8067 Can you explain more?
So clear
Awesome !
Shouldn't it be (b U (b a*)*) since we can loop as many times as we wish over q0 after removing q2 ?
Great video!!
Great video :)
Super.💪🤟
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)?
Thanks! What do you mean by "universe"?
@@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.
@@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.
@@EasyTheory thank you, I really appreciate your response!
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 ?
Sir why did you put whole * in last step (rip q0) but why no * for a in Rio q1
There was no self-loop for q1, so no * is added there.
How do you find regex given an nfa with multiple accepting states?
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.
I ripped q1 first and got a shorter, different result: (b∪ba*a)*a is it wrong?
Is there any way to find minimal regex?
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.
@@EasyTheory wow!! Thanks.
Can we do this for DFA`s?
you are the best lol
@@beyinforum Thanks! And yes you can. Just use the same idea as this video (the machine doesn't have to be deterministic)
Hiiiii