Regular Expression (Regex) to NFA Example Conversion

Here we give an example on the regular expression (regex) to NFA proof we did in the last video, which is here: • Regular Expression (Re...
If you like this content, please consider subscribing to my channel: / @easytheory
▶SEND ME THEORY QUESTIONS◀
[e-mail]
▶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.

[@michaelwolfman8432]

I am very late to the party here, but thank you so much for this video! You posed the question: "what is the NFA for R = ab"? Is this the correct answer: - -> q1 - - a - - > q2 - - ε - - q3 - - b - - > q4 (final state)

[@nolegit2294]

I beleive so

[@thimethimesha8495]

best explanation which I saw sir..

[@olowofilasamuel9434]

You made a mistake at the end. Closure has a transition going from the accept state to the start state of (a ∪ b) and not to the newly introduced start state (which also doubles as an accept state)

[@antoniohenriquefigueiralou9771]

I believe the result will be the same. You may test both options using the jflap program. Draw the two versions and convert them to DFA. We will likely have identical DFAs.

[@Imperialcodex1]

Thanks alot

[@vimalathithand917]

Nice example!

[@adhamsakr1946]

ure amazing i swear

[@GabrielOduori]

Right in the middle of my TOC course and your videos are sublime! Lets tweak it a little bit and say instead of a \cup b, we had a^*b^*, how would the transition from a^* accept state to the b^* start state be?

[@EasyTheory]

Make sure to watch all the videos as fast as possible, and share with all your friends! :) I would think about a* first. How would you create it? You start with an NFA for just a, and then do the star operation on it (giving three states, two are final). Then do the same for b*. Then the epsilon transitions would be from those 2 final states of a* to the start of the one for b*.

[@GabrielOduori]

@@EasyTheory Thank you very much for the response. The epsilon transition from a* two accept states (which now changes to a transition state) to the start state of b* does make it work.

[@OLYMPICx22x]

I think you missed an epsilon path. One should show an empty set: going from first state to final state.

[@EasyTheory]

I don't think so, since the first state was for the outer *. What timestamp is what you're referring to?

[@OLYMPICx22x]

@@EasyTheory 6:35 I'm referring to the fact that *on the furthest out parenthesis means that an empty set with no characters should go straight to the final state. So it would need a direct epsilon transition from initial state to accepting state. I hope that clarifies it

[@EasyTheory]

@@OLYMPICx22x Note that it's an empty string, not empty set. And I think you're misunderstanding the * operation - it's 0 or more occurrences of picking some string the "inside" can make. This means that either we read the empty string (and we're done), or we "go through the machine", and allow ourselves to do it again if we please. The green start state here at the beginning is final for the first reason, that if we are given the empty string, we allow ourselves to stop there (this is where the nondeterminism comes in). If not, then we cannot just stop at this start state since we must read the entire string in order to accept. You're technically right that we are *allowed* to make an epsilon transition straight to the far right green final state, but this is not the point of the method, in that this procedure works for *any* regular expression. Just because it works in this particular case does not mean it will work in general (although it may be possible! Can you prove or disprove it?)

[@antoniohenriquefigueiralou9771]

I believe the result will be the same. You may test the three options using the jflap program. Draw the three versions and convert them to DFA. We will likely have identical DFAs. The versions are: no-epsilon-transition (made in the video); with epsilon-transition from the new initial state and with epsilon-transition from the modified initial state (without this being accepting).

[@angelgabriel9880]

Como pasarla vida?

[@raghadfahad211]

save my life