Преобразование регулярного выражения в ДКА

Question

Я пытался конвертировать регулярное выражение

в недетерминированных конечных автоматов (NFA) первое с использованием конструкции Томпсона, давая:

, который выглядит правильно.

Затем я использую построение подмножества для создания DFA из NFA, показанного здесь.

Но это не выглядит правильно для меня, как, например, 0, затем 0 не является действительным в соответствии с DFA я построил. Мне было интересно, как я должен моделировать epsilon в исходном регулярном выражении, поскольку я просто рассматривал его как обычный эпсилон.

Answer 1

Одно совпадение уже - таким образом состояние B в вашей диаграмме для dfa должно быть уже принимающим состоянием (просто отметьте его, как принятие не исправит его!). Я не могу восстановить свои идеи, но вы должны закончить в чем-то вроде

A --0--> (B) 
A --1--> C 
B --0--> (B) 
B --1--> C 
C --0--> (B) 
C --1--> C 

---

Если вы начнете думать, с другой стороны, регулярное выражение (0|)(0|1)*0 может быть упрощена путем удаления первой части (0|). Это можно сделать, потому что (0|1) соответствует всем, что соответствует (0|) (и больше). Вы также можете увидеть его на диаграмме для nfa.

S0->S1->S2->S5 === S7->S7->S8->S11 
S0->S3->S4->S5 === epsilon 

Может быть, это может помочь получить ваши мысли в правильном направлении ..