Введение в схемы, автоматы и алгоритмы



             

Недетерминированные конечные автоматы и их детерминизация - часть 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.

 Диаграмма автомата N1

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

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




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