Недетерминированные конечные автоматы и их детерминизация - часть 2

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

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

$p'=e_{j_1}e_{j_2} \ldots e_{j_t}$

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

$e_{j_i}\ (1 \leq i \leq t)$

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

$\varepsilon^{k_1}w_1\varepsilon^{k_2}w_2 \ldots \varepsilon^{k_t}w_t \varepsilon^{k_{t+1}}$

, где kj

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

$\ t + \sum_{j=1}^{t+1} k_j = T$

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

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

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

Q и w

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

$\vdash_M$

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

$(q, w) \vdash_M (q^\prime, w^\prime)\ \Leftrightarrow \ (w = aw^\prime \textit{ и } q^\prime \in \Phi(q,a) )$

или

$( w = w^\prime и q^\prime \in \Phi(q,\varepsilon)).$

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

$\vdash_M^*$

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

$\vdash_M$

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

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

$q \in F$

$(q_0, w) \vdash_M^* (q, \varepsilon)$

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

$L_M= \{ w\ |\ M \text{ распознает } \ w\}$

Отличие состоит в том, что у НКА может быть несколько различных способов работы (путей вычисления) на одном и том же входном слове 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}

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

$D_{N_1}$

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

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

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

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