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


           

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


Скажем, что заданный последовательностью ребер путь 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:


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





Forekc.ru
Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий