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

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

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

введите здесь описание изображения

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

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

введите здесь описание изображения

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


regex compiler-construction dfa computation-theory nfa
person AkshaiShah    schedule 05.05.2015    source источник
comment
Это принадлежит cs.stackexchange.com   -  person Hexaholic    schedule 05.05.2015
comment
В вашем регулярном выражении отсутствует скобка?   -  person Bergi    schedule 05.05.2015
comment
@ Берги, да, это так. на картинке показано правильное регулярное выражение   -  person AkshaiShah    schedule 05.05.2015

Ответы (1)


arrow_upward
0
arrow_downward

Одиночное совпадение уже - таким образом, состояние 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

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

person Wolfgang Kluge    schedule 18.05.2015