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


             

и задают как список из


Функцию ? называют программой автомата A и задают как список из m n команд вида qiaj
?(qi,aj) .

Удобно также задавать функцию ? с помощью описанной выше таблицы размера n ? m, строки которой соответствуют состояниям из Q, а столбцы - символам из входного алфавита ?, и в которой на пересечении строки qi и столбца aj стоит состояние ?(qi,aj).

Как и автоматы-преобразователи, автоматы-распознаватели можно представлять с помощью размеченных ориентированных графов, называемых диаграммами.

Определение 4.4.

Диаграмма ДКА A = <?, Q, q0, ? > - это ориентированный (мульти)граф DA=(Q, E) с помеченными ребрами, в котором выделена вершина-начальное состояние q0 из каждой вершины q
Q выходит |?X| ребер, помеченных символами a
? так, что для каждой q
Q и каждого символа a
? имеется единственное ребро из q в вершину q' =?(q,a) с меткой a .

Скажем, что представленный последовательностью ребер путь p=e1e2 … et в диаграмме несет слово w=w1w2 … wt, если wi - это метка ребра ei (1
i
t). Если q - начальная вершина (состояние) этого пути, а q' - его заключительная вершина, то будем говорить, что слово w переводит q в q'.

Работа конечного автомата-распознавателя состоит в чтении входного слова и изменению состояний в зависимости от его символов.

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

На множестве конфигураций введем отношение перехода за один шаг
:



Если w=?, то положим для каждого q
Q: (q, ?)
(q, ?).

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

Содержательно,
означает, что автомат A, начав работу в состоянии q на слове w=w1 … wl, через некоторое конечное число шагов 0
k
l прочтет первые k символов слова w и перейдет в состояние q', а w' =wk+1 … wl - это непрочтенный остаток слова w.

Определение 4.6.

ДКА A распознает (допускает, принимает) слово w, если для некоторого q
F

, т.е. после обработки слова w автомат переходит в принимающее состояние.

Язык LA, распознаваемый (допускаемый, принимаемый) автоматом A, состоит из всех слов, распознаваемых этим автоматом:


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