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

Подписаться 27 тыс.

Просмотров 47 тыс.

50% 1

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.

Опубликовано:

15 сен 2024

Ссылка:

Скачать:

Готовим ссылку...

Добавить в:

Мой плейлист

Посмотреть позже

Комментарии : 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 2 дня назад

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?

@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 :))

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