What is the NFA to DFA conversion? (Sipser 1.17 Solution)

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

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

50% 1

Here we do an example of the NFA to DFA conversion, otherwise known as the "powerset construction", which solves problem 1.17 in the Sipser textbook. The problem first asks to create an NFA for the given regex, which is easy enough to do.
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.

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

17 сен 2024

Ссылка:

Скачать:

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

Добавить в:

Мой плейлист

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

Комментарии : 6

@EasyTheory 2 года назад

Addendum: I forgot the 1 transition from the 12 state, which should go to the emptyset state. Sorry about that!

@hubukitako9927 2 года назад

Well, there's a litte mistake. the regex on the book is 01U001U010, not 01U011U010. the same process though

@soup4668 11 месяцев назад

Im confused. At the 1235 state on 0 transition, we can get from 2 to 3 which I understand. But we are also in 5 which should mean through epsilon transition that we are also in 1 and 2. So why is 1235 only going to 3 if we can reach 123 from 1235? Why do you say 5 goes nowhere? same with 125 on 1 transition, why does that go to the empty set when 5 can take us to 1 and 2?