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

Пусть ?={a1, …, am} - это алфавит, который состоит из конечного множества элементов, называемых символами (буквами).

Слово в алфавите ? - это конечная последовательность символов этого алфавита: w =w1… wn, wi

? при i=1, …, n. Число букв в этой последовательности называется длиной слова и обозначается |w|. Имеется одно специальное "пустое" слово длины 0. Будем обозначать его через ?. На словах определена операция приписывания одного слова после другого, называемая конкатенацией: если слово w =w1… wn, а слово v =v1… vm, то их конкатенация w ? v - это слово w1… wnv1… vm длины n+m. Обычно знак конкатенации ? будем опускать и писать просто w v (по аналогии со знаком умножения в алгебре). Пустое слово - это единственное слово такое, что для любого слова w справедливо равенство w ?= ? w = w. Операция конкатенации ассоциативна: для любых трех слов w, v и u, очевидно, имеет место равенство: (w v)u = w(v u). Поэтому скобки при записи конкатенации нескольких слов будем опускать. Для представления нескольких конкатенаций одного и того же слова используют сокращенную "степенную форму" записи: w0 = ?, w1= w,…, wi+1 = wiw. Например, a3b4c2 - это сокращенная запись слова aaabbbbcc.

Языком в алфавите ? называется произвольное множество слов этого алфавита . Язык, включающий все слова в алфавите ? ( в том числе и пустое слово ?), будем обозначать через ?*.

Конечные автоматы часто используются для определения тех или иных свойств слов, т.е. для распознавания языков: автомат, распознающий некоторый язык L должен по произвольному слову w ответить на вопрос " w

L? ". Для решения такой задачи функция выходов может быть заменена на проверку того, в какое состояние переходит автомат после получения входного слова w - "принимающее" или "отвергающее".

Определение 4.3. Детерминированный конечный автомат (ДКА) - распознаватель - это система вида

включающая следующие компоненты:

? ={a1, … , am} (m
1) - конечное множество - входной алфавит;
Q={q0, … , qn-1} (n
1) - конечное множество - алфавит внутренних состояний;
q0
Q - начальное состояние автомата;
F
Q - множество принимающих (допускающих, заключительных) состояний;
?: Q ? ?
Q - функция переходов,
?(q, a) - это состояние, в которое переходит автомат из состояния q, когда получает на вход символ a.

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

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

l прочтет первые k символов слова w и перейдет в состояние q', а w' =wk+1 … wl - это непрочтенный остаток слова w.

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

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

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

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

Язык называется конечно автоматным, если он распознается некоторым ДКА.

Из этого определения, в частности, следует, что ?

F. Один и тот же язык может распознаваться разными автоматами.

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

Автоматы A и B называются эквивалентными, если совпадают распознаваемые ими языки, т.е. LA = LB.

Определение распознавания слова и языка можно легко перевести на язык диаграмм.

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

F в диаграмме DA имеется путь из q0 в q, который несет слово w, т.е. w переводит q0 в заключительное состояние q.

Доказательство можно провести индукцией по длине слова w (см. задачу 4.3).

Tаким образом, язык LA, распознаваемый автоматом A, состоит из всех слов, которые переводят в его диаграмме DA начальное состояние q0 в заключительные состояния из F.

Наша цель теперь состоит в изучении класса конечно автоматных языков.

Во многих случаях удается доказать, что язык L конечно автоматный, непосредственно построив распознающий его автомат. Для этого нужно постараться разбить множество всех входных слов на конечное число классов "однородных", "эквивалентных" слов, т.е. слов, получение которых на входе одинаково влияет на возможность их продолжения до слов распознавемого языка. Затем для каждого такого класса создать состояние автомата и определить переходы между этими состояниями. Часто полезно бывает выделить одно состояние для представления "ошибочных" слов, для которых ни они сами, ни любые их продолжения не входят в язык.

Содержание раздела