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

Here we do an example of the regular expression to nondeterministic finite automaton (NFA) conversion. The basic idea is to make a small NFA for the "indivisible" pieces, then combine them using union, concatenation, and star as the case may be.
Easy Theory Website: www.easytheory.org
Discord: / discord
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.

[@cristianiorga6393]

You are amazing! It`s a shame I only discovered your channel in the night before the exam :D

[@ashwath2324]

simple and well explained

[@christio02]

Thank you so much! Very good explanation and procedure!

[@dawidbania7903]

There is a mistake in constructing the expression (abb)*. With the way you described it, you can make expressions that are of form (abb)^n where n>=1. There should be a returning loop between last state (that we get into by reading 'b' for the second time) and the state before we read 'a' with 'epsilon' read. And there should be a forward path from starting state to end state with 'epsilon' read.

[@rusokemarvin]

yes, this is very right. I was looking out for a comment that matches my thought. Thanks

[@chongwan4712]

I think what Easy Theory had was correct.
First, you're saying that "There should be a returning loop between last state (that we get into by reading 'b' for the second time) and the state before we read 'a' with 'epsilon' read" but this is equivalent to linking the last state to the beginning state because epsilon transitions don't take up any string.
Second, responding to the statement "And there should be a forward path from starting state to end state with 'epsilon' read.", this is redundant because the starting state is already a final state, so we don't need the epsilon transition to the end state.
Please correct me if you think I am wrong.

[@Karim-nq1be]

That was easy indeed and brilliantly explained.

[@christianhackelman303]

Awesome and explained clearly, thank you!

[@MiguelMartinez-yj7yu]

You're amazing, man!

[@moeyali123]

Thanks I learnt a lot from your videos

[@seiftarraf6213]

Very helpful. Thank you. This converted the regex into an epsilon-NFA. Now I could convert this epsilon-NFA into an NFA but this would take even more time. Do you have any tips on how to convert this regex into an NFA without epsilon-transitions?

[@yuxiaoliu806]

Thank you!

[@supamdeepbains5172]

Thank you, I'd request please more pumping lemmas problems :)

[@raywei1701]

great explanation as always!

[@benjaminwatkinson6464]

If NFAs are like onions and ogres are like onions can you convert directly from NFAs to ogres?

[@anthonyevans8536]

you're asking the right questions here!

[@deepakjain4481]

thanks a lot thanks a lot you are my saviour i was so stressed

[@NabeghMuhra]

Thanks, very helpful!!

[@carina.zip2002]

this made so much sense than you so much!! really helping me in my algo analysis class :))

[@mix_tutorial_gaming2985]

You are my savior.

[@camdenwyeth316]

Thanks! This was helpful :D

[@golden-jungoo655]

Thank you so much ^^

[@dharmashah4832]

Amazing thank u so so much

[@twishaanshu8100]

how would you convert this to left linear grammar? with all the Epsilons?

[@zeynepbasoglu3426]

great video 😍

[@robzonefire]

THANK U MAN U ROCK

[@bulentdayoglu7310]

ty

[@taha5539]

Can we get rid of some of the epsilons?

[@user-uz7xk8ov1i]

this video will be my source for compiler class lmao

[@CK-od6ig]

If we had the regular expression a(abb)* U c and instead of b we put c in place of the corresponding b in the NFA how would the NFA accept for example the string αc ?

[@pedromartins5695]

It doesn't. The strings accepted would be {EMPTY, c, a, aabb, aabbabb,...}. It's the union of the unitary string 'c' and the strings generated bu the regular expression a(abb)*, that is, string that start with 'a' and has any amount of 'abb's, even none.

[@KevinGarcia-ws1kt]

is the union and the Plus sign the same ??

[@erky195]

yes

[@azerchniti9497]

barra yarham bouk

[@user-yv1jr5oo8h]

Go to an indian teacher they are very good in teaching..

[@ALIENGOATMESSI]

complicated thiongs

[@azerchniti9497]

that was eazzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzi