Скажем, что заданный последовательностью ребер путь p=e1e2 … eT в диаграмме DM несет слово w=w1w2 … wt (t
Слово w переводит q в q' в диаграмме DM, если в ней имеется путь из q в q' который несет w .
На недетерминированные автоматы естественным образом переносится определение конфигураций и отношения перехода между ними.
Определение 4.9. Назовем конфигурацией НКА M = <?, Q, q0, F, ?, > произвольную пару вида (q, w), в которой q
или
Как и для ДКА, через
Внешне определение распознавания слов НКА совпадает с определением для ДКА.
Определение 4.10. НКА M распознает (допускает, принимает) слово w, если для некоторого
Язык LM, распознаваемый НКА M, состоит из всех слов, распознаваемых автоматом:
Отличие состоит в том, что у НКА может быть несколько различных способов работы (путей вычисления) на одном и том же входном слове w. Считаем, что НКА распознает (допускает, принимает) это слово, если хотя бы один из этих способов приводит в заключительное состояние из F.
Из определения диаграммы DM непосредственно следует, что НКА M распознает слово w, тогда и только тогда, когда существует такое заключительное состояние q
Пример 4.1. Рассмотрим НКА N1 = < {a, b}, {0,1,2,3, 4}, 0, {3}, ?>, где
0 | {0,1} | {0} | ![]() |
1 | ![]() | ![]() | {4} |
2 | {3} | ![]() | ![]() |
3 | ![]() | ![]() | {1} |
4 | ![]() | {2} | ![]() |
Его диаграмма
Рассмотрим работу этого автомата на слове ababa: