преобразования регулярных выражений в DFSA

Я изучаю процесс, преобразующий регулярное выражение DFSA. Я встретил регулярное выражение a | bc * d и сделал так dfsa.

но http://hackingoff.com/compilers/regular-expression-to-nfa-dfa

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

Есть ли разница между ними? это мой dfsa не так?

источник

2016-05-02 Youngin Na

Конечно ваша содержит ошибку, потому что после согласования b, регулярное выражение двигатель может соответствовать d сразу после, как c* может соответствовать пустой строке (c может отсутствовать между b и d).

Калькулятор * соответствует 0 или более вхождениям в соответствие с предыдущим подшаблоном (группа, класс символов, буквальный символ).

a|bc*d 
0| || | 
1 || | 
    || | 
    2| | 
    3 | 
     4

источник

2016-05-02 08:14:26

Я думаю, что именно поэтому есть возможность перейти от 2 до 4, не дойдя до 3? Это неправильно? – AbhiNickz

Именно поэтому существует «прямой маршрут» от 'b' до' d' (от 2 до 4). 'c *' является полностью необязательным. –

, но мой тоже поймать, что c может быть пропущен. Я имею в виду, если вы находитесь в состоянии 2, fsa может просто не читать «c» и просто перейти прямо к d. Если я правильно понял, даже думал, что производные строки такие же, но регулярное выражение «bc * d» должно быть полностью интерпретировано. Итак, в моем dfsa можно перейти через b после d, не читая c. Я правильно понял? –

преобразования регулярных выражений в DFSA

ответ

Смежные вопросы