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

Рет қаралды 46,840

Күн бұрын

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◀
ryan.e.dougherty@icloud.com
▶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.

Пікірлер: 39

@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 6 ай бұрын

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

@chongwan4712 5 ай бұрын

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.

@benjaminwatkinson6464 2 жыл бұрын

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

@anthonyevans8536 2 жыл бұрын

you're asking the right questions here!

@annafebland4460 3 күн бұрын

Thank you! Very easy to understand ❤❤❤

@seiftarraf6213 2 жыл бұрын

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?

@mix_tutorial_gaming2985 Жыл бұрын

You are my savior.

@deepakjain4481 9 ай бұрын

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

@carina.zip2002 8 ай бұрын

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

@chackelman 2 жыл бұрын

Awesome and explained clearly, thank you!

@christio02 Жыл бұрын

Thank you so much! Very good explanation and procedure!

@raywei1701 5 ай бұрын

great explanation as always!

@Karim-nq1be Жыл бұрын

That was easy indeed and brilliantly explained.

@ashwath2324 2 жыл бұрын

simple and well explained

@supamdeepbains5172 2 жыл бұрын

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

@NabeghMuhra 5 ай бұрын

Thanks, very helpful!!

@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 11 ай бұрын

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.