Преобразование RE -> NFA - PullRequest
0 голосов
/ 09 мая 2011

У меня есть вопрос относительно преобразования регулярных выражений в недетерминированные автоматы с конечным состоянием:

Преобразование (a * | b *) * в NFA.Моя попытка заключается в следующем:

enter image description here

Я полностью не в курсе?Или что-то есть?

Примечание: E => ε

1 Ответ

3 голосов
/ 09 мая 2011

Ваш NFA соответствует тому же языку, что и (a*|b*)*, поэтому ответ правильный.

Однако есть много NFA, которые соответствуют одному и тому же языку, и в вашем случае можно было бы удалить как минимум три эпсилон-стрелки. Тем не менее, это не будет более правильным, чем ваше предложение.

Регулярное выражение (a*|b*)* также может быть упрощено без изменения семантики. Например. (a|b)* эквивалентно (a*|b*)*. И если вы думаете об этом, FA может быть так просто, как это:

Finite Automaton equivalent to (a|b)*

...