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



             

Детерминированные конечные автоматы (ДКА) и автоматные языки - часть 2


Функцию ? называют программой автомата 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
?*.

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

\vdash_A
:

(q, w) \vdash_A (q^\prime, w^\prime)\ \Leftrightarrow\ w = aw^\prime, \ \Phi(q,a)= q^\prime

Если w=?, то положим для каждого q

Q: (q, ?)
\vdash_A
(q, ?).

Через

\vdash_A^*
обозначим рефлексивное и транзитивное замыкание
\vdash_A
.

Содержательно,

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

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

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

F

(q_0, w) \vdash_A^* (q, \varepsilon)
, т.е. после обработки слова w автомат переходит в принимающее состояние.

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




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