Как конвертировать (ab u aab u aba)* в NFA?

Question

Как конвертировать (ab u aab u aba)* в NFA?

(ab u aab u aba)*

Я сделал это, но я хотел бы получить некоторые отзывы о его правильности:

Если это правильно: Можем ли мы упростить (ab u aab u aba)* дальше?

Если нет: что я пропустил?

РЕДАКТИРОВАТЬ: Кажется, мне не хватает электронных переходов из всех трех конечных состояний обратно в начальное состояние, и мне нужно новое состояние, начальное и конечное, которое перейдет в старое начальное состояние при электронном переходе. (Правило Клини Стар).

PS Можем ли мы также упростить (a u b)*aabab а также (a u b)*a(a u b)(a u b)(a u b)(a u b),

Причина, по которой я спрашиваю, потому что если нет способа упростить / минимизировать, это будет смехотворно длинный DFA...

0

regex finite-automata dfa nfa

Источник

user274117 17 окт '11 в 22:38

1 ответ

Решение

Другие вопросы по тегам regex finite-automata dfa nfa

user182705 17 окт '11 в 22:59 2011-10-17 22:59 · Accepted Answer · 2011-10-17 22:59

Я вижу небольшое упрощение вашего первого случая в том, что вы можете написать его как (a(b u ab u ba))*, но это не обязательно поможет. Я все еще думаю, что вашему DFA не понадобится столько штатов, сколько вы думаете.

В обоих последних случаях потребуются DFA с 32 состояниями, чтобы отслеживать последние 5 прочитанных символов. Разница в том, что второй DFA имеет только одно конечное состояние, а третий DFA имеет 16.