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...
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

[@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.

[@louis9116]

It's a standard procedure. Don't make things more complicated

[@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!

[@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?

[@deepakjain4481]

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

[@carina.zip2002]

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

[@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.

[@taha5539]

Can we get rid of some of the epsilons?

[@mix_tutorial_gaming2985]

You are my savior.

[@christio02]

Thank you so much! Very good explanation and procedure!

[@Karim-nq1be]

That was easy indeed and brilliantly explained.

[@annafebland4460]

Thank you! Very easy to understand ❤❤❤

[@supamdeepbains5172]

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

[@twishaanshu8100]

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

[@raywei1701]

great explanation as always!

[@ashwath2324]

simple and well explained

[@chackelman]

Awesome and explained clearly, thank you!

[@KevinGarcia-ws1kt]

is the union and the Plus sign the same ??

[@erky195]

yes

[@NabeghMuhra]

Thanks, very helpful!!

[@MUSHIN_888]

Thanks I learnt a lot from your videos

[@golden-jungoo655]

Thank you so much ^^

[@최현아-i4n]

this video will be my source for compiler class lmao

[@camdenwyeth316]

Thanks! This was helpful :D

[@MiguelMartinez-yj7yu]

You're amazing, man!

[@zeynepbasoglu3426]

great video 😍

[@yuxiaoliu806]

Thank you!

[@dharmashah4832]

Amazing thank u so so much

[@robzonefire]

THANK U MAN U ROCK

[@bulentdayoglu7310]

ty

[@azerchniti9497]

barra yarham bouk

[@THEoneandonlystika]

complicated thiongs

[@azerchniti9497]

that was eazzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzi

[@Googlinghelpers]

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

[@ConradRobert-y3q]

6997 Jerrod Overpass