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