что заданный последовательностью ребер путь

Скажем, что заданный последовательностью ребер путь p=e1e2 … eT в диаграмме DM несет слово w=w1w2 … wt (t

T), если после удаления из него "пустых" ребер (т.е. ребер с метками ?) остается последовательность из t ребер

, метки которых образуют слово w , т.е. wi - это метка ребра

. Очевидно, это эквивалентно тому, что последовательность меток на ребрах пути p имеет вид

, где kj

0 (j=1,2, … , t+1) и

.

Слово w переводит q в q' в диаграмме DM, если в ней имеется путь из q в q' который несет w .

На недетерминированные автоматы естественным образом переносится определение конфигураций и отношения перехода между ними.

Определение 4.9. Назовем конфигурацией НКА M = <?, Q, q0, F, ?, > произвольную пару вида (q, w), в которой q

Q и w

?*. Определим отношение

перехода из одной конфигурации в другую за один шаг:

или

Как и для ДКА, через

обозначим рефлексивное и транзитивное замыкание отношения

.

Внешне определение распознавания слов НКА совпадает с определением для ДКА.

Определение 4.10. НКА M распознает (допускает, принимает) слово w, если для некоторого

.

Язык LM, распознаваемый НКА M, состоит из всех слов, распознаваемых автоматом:

Отличие состоит в том, что у НКА может быть несколько различных способов работы (путей вычисления) на одном и том же входном слове w. Считаем, что НКА распознает (допускает, принимает) это слово, если хотя бы один из этих способов приводит в заключительное состояние из F.

Из определения диаграммы DM непосредственно следует, что НКА M распознает слово w, тогда и только тогда, когда существует такое заключительное состояние q

F, что в диаграмме DM слово w переводит q0 в q. Иными словами, в DM имеется путь из q0 в q, на ребрах которого написано слово w (с точностью до меток ?).

Пример 4.1. Рассмотрим НКА N1 = < {a, b}, {0,1,2,3, 4}, 0, {3}, ?>, где

?:Q\?Xab?

0	{0,1}	{0}
1			{4}
2	{3}
3			{1}
4		{2}

Его диаграмма

представлена ниже на рис. 4.3.

Рис. 4.3. Диаграмма автомата N1

Рассмотрим работу этого автомата на слове ababa:

Содержание Назад Вперед