Вы ничего не упускаете, но NFA можно значительно упростить, свернув пути и исключив λ-правила.Чтобы определить, определяет ли ваш NFA язык, обозначаемый регулярным выражением, вы можете неформально спорить, гоняясь за состояниями в графе переходов.Чтобы поговорить о NFA, я буду использовать следующее определение функции δ с конечными состояниями {q 0 , q 3 , q 4 }и начальное состояние q 0
- δ (q 0 , a) = {q 1 , q 2 }
- δ (q 1 , a) = {q 2 }
- δ (q 2 ,б) = {q 3 }
- δ (q 3 , а) = {q 4 }
- δ(q 3 , λ) = {q 0 }
- δ (q 4 , λ) = {q - }
Цель состоит в том, чтобы показать, что NFA принимает именно язык (ab U aab U aba) *.С этой целью мы можем рассмотреть принятые строки, начав с λ при q 0 и исчерпав все возможные переходы через график, записав строки, построенные путем объединения символов, на которые переходили, и отметив, является ли такая строкапринято или нет.Пути в графе указывают на конкатенацию;конечные состояния указывают на принятие или дизъюнкцию;петли указывают звезду Клини.
От q 0 и λ мы можем перейти от a к q 1 или q 2 .На q 1 и a мы можем перейти к q 2 .Следовательно, на q 2 мы имеем либо a или aa и ничего больше.От q 2 и a или aa мы можем перейти к q 3 на b .Следовательно, при q 3 мы имеем либо ab или aab и ничего больше.От q 3 и ab или aab мы можем перейти к q 0 на λ или q 4 на а .Следовательно, на q 3 и ab или aab мы имеем либо ab , либо aab , либо aba и ничего больше.Наконец, на q 4 и aba мы можем перейти к q 0 на λ.Так как у нас есть ab или aab или aba и мы перешли в начальное состояние, то есть наш вывод может повторяться ноль или более раз, и мы исчерпали возможныепереходы, мы заключаем, что NFA решает замыкание Клини ab или aab или aba .
Существуют более формальные методыпоказать, что данный NFA решает язык.Но самый простой способ - исчерпать все возможные пути через NFA, вводя замыкания Клини на циклах.Примером формального метода может быть преобразование NFA в регулярное выражение, а затем аксиоматическое получение равенства полученного выражения и целевого выражения.Это в основном не нужно.
Вы, вероятно, сделали именно то, что я только что написал, однако, сделав весь этот пост ненужным.Если нет, я надеюсь, что это показывает неформальные рассуждения, которые вы можете использовать, чтобы убедить себя, что NFA решает язык.