Regular Expression (Regex) to NFA Conversion

Here we cover the regular expression (regex) to NFA conversion. The idea is to revisit the definition of regex, and to make an NFA for each of the 6 pieces of the definition. For the first three, we can make either a 1-state or a 2-state NFA. For the other three (the "inductive" cases), we revisit earlier constructions with NFAs using union, concatenation, and star to make an NFA for the "bigger" regex, using "smaller" NFAs that have already been built.
If you like this content, please consider subscribing to my channel: / @easytheory
▶ADDITIONAL QUESTIONS◀
1. What does the NFA for the regex ab look like?
▶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.

[@emreastarc6734]

Oh man this is well refined explanation of topic. No empty talk or skipping explanations. Kudos for the using boxes as abstraction. That makes easier to comprehend the topic.

[@necati3656]

Your narration is very simple and successful. Simplifying the narration with boxes made the subject much easier.

[@EasyTheory]

Thanks!

[@rainysummer7776]

In Germany we call you Ehrenmann, because you saved us from failing the exam

[@EasyTheory]

Much appreciated

[@pierrejacomet8098]

Excellent video, very informative. A couple of suggestions for the next round: At stage 4 (union), in addition to the two epsilon transitions for the alternatives, you may want to add two final epsilon transitions to a single new final state. That would mean in step 5 (concatenation) instead of drawing two epsilon transitions to the next state, you would draw just one, showing better the concatenation effect. By the same reasoning, this would save you one epsilon transition in step 6 (iteration) as you'd need to go from the single end state back to the beginning state to represent the + repetition.

[@vimalathithand917]

An execptional explanation of the subject. Thanks a lot !if it weren't u i would have been soo hard to understand these.Great work

[@EvanSmith-de9cd]

Thank you for making this video. Really helped me get a better understanding

[@ngocchaunguyen8685]

Sir, appreciate your videos!

[@안수진-b4p]

so insightful course! THank you.. I was having a hard time understanding and applying this concept, but after I watched this, my confusing point was clarified!! Thanks

[@sa1dzhan]

Amazing explanation!

[@johnnymark4643]

This is easier to understand after watching the DFA/NFA to regex conversion video in my opinion.

[@EasyTheory]

Definitely!

[@ibrahimkoz1983]

Excellent.

[@bbydinobeats]

u r a fookin legend thank you

[@michaelwolfman8432]

Great Video! Why do we add a new starting state when doing the Kleene Closure operation? Does it have something to do with its recursive definition?

[@user-dj9iu2et3r]

This video helped, for sure… but it would have been cool to see you work through one or two examples, at least!

[@Amin-ve2xs]

What if: L= { w in {0,1}* |#1 (w) is odd and for every u in {0,1}* : w /= u1} how could it be?
I tought, it might be 0*10 | 0*10*10*10 . Is it right ?

[@samjudelson]

Thanks!

[@jeansoto6046]

Excellent video! could u upload a pdf of the all you've done in this video and the one of the example?

[@satshah1492]

For kleene star why do you make the new start state a final state

[@rainysummer7776]

i dunno if you still lookup for the answer, but anyways: you need the new start state to be a final state, because with Kleene star you can also create the empty word epsilon.

[@archanatripathi6616]

@@rainysummer7776 so why don't make the start state also an accept state?

[@archanatripathi6616]

I meant the original start state instead of adding another state

[@putrescentvermin]

Yeah the accept states are supposed to point towards the original start state not the newly made start state.

[@alanchang3577]

@@archanatripathi6616 I found a pretty solid answer from the internet: Consider a two state automaton for the language 𝑎∗𝑏, two transitions from the initial state, one looping with label 𝑎, the other with label 𝑏 to the final state.
Making the initial state final, would also accept 𝑎∗.

[@Anonymous-nz8wd]

thanks for the video

[@EasyTheory]

You're welcome

[@lowerbound4803]

The role of epsilon is a merger right?

[@jesse2436]

and it turns out yes we can

[@Suvanch]

too many ads