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

Пусть ?={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 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, состоит из всех слов, распознаваемых этим автоматом:





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

Из этого определения, в частности, следует, что ? LA q0 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 конечно автоматный, непосредственно построив распознающий его автомат. Для этого нужно постараться разбить множество всех входных слов на конечное число классов "однородных", "эквивалентных" слов, т.е. слов, получение которых на входе одинаково влияет на возможность их продолжения до слов распознавемого языка. Затем для каждого такого класса создать состояние автомата и определить переходы между этими состояниями. Часто полезно бывает выделить одно состояние для представления "ошибочных" слов, для которых ни они сами, ни любые их продолжения не входят в язык.

Недетерминированные конечные автоматы и их детерминизация

Недетерминированные конечные автоматы, рассматриваемые в этом параграфе, являются обобщениями детерминированных: они при чтении очередного символа на входе могут выбрать в качестве следующего одно из нескольких состояний, а кроме того, могут изменить состояние без чтения входа. Основной результат, который мы установим, утверждает, что это обощение не существенно: недетерминированные и детерминированные конечные автоматы распознают одни и те же языки.

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

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

? ={a1, … , am} (m

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

Для a

? значение ?(q, a) - это множество состояний в каждое из которых может перейти автомат из состояния q, когда получает на вход символ a. ?(q, ?) - это множество состояний в каждое из которых может перейти автомат из состояния q без чтения символа на входе.

Как и для детерминированных автоматов, функцию переходов можно представить с помощью набора команд-программы: для каждой пары q

Q и a ? и каждого состояния q' ?(q, a) в программу помещается команда q a q', и для каждого состояния q' ?(q, ?) в программу помещается команда q q'. Отличие от детерминированного случая состоит в том, что для одной пары q Q и a ? в программе может быть несколько команд вида q a q' или не быть ни одной такой команды. Кроме того, могут появиться ?-команды (пустые переходы) вида q q', означающие возможность непосредственного перехода из q в q' без чтения символа на входе.

При табличном задании функции ? в таблице появляется (m+1)-ый столбец, соответствующий пустому символу ? и на пересечении строки q и столбца a

(? {?}) стоит множество состояний ?(q,a).

Для недетерминированного автомата M = <?, Q, q0, ? > в диаграмме DM=(Q, E) с выделенной начальной вершиной q0 и множеством заключительных вершин F ребра взаимно-однозначно соответствуют командам: команде вида q a

q' (a ?) соответствует ребро (q,q'), с меткой a , а команде вида q q' соответствует ребро (q,q'), с меткой ?.

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





Так как 3 - заключительное состояние, то ababa LN1. Заметим, что у автомата N1 имеются и другие способы работы на этом слове, не ведущие к заключительному состоянию. Например, он может после чтения каждого символа оставаться в состоянии 0. Но чтобы слово допускалось, достаточно существовать хотя бы одному "хорошему" способу.

Очевидно, что детерминированные конечные автоматы являются частными случаями недетерминированных. Естественно спросить, распознают ли недетерминированные конечные автоматы больший класс языков чем детерминированные? Следующая теорема показывает, что классы языков, распознаваемых НКА и ДКА совпадают.

Теорема 4.2. (Детерминизация НКА)

Для каждого НКА M можно эффективно построить такой ДКА A, что LA = LM.

Доказательство Пусть M= <?, Q, q0, F, ? > - НКА. Процедура построения по нему эквивалентного ДКА состоит из двух этапов: на первом по M строится эквивалентный ему НКА M1, в программе которого отсутствуют переходы по ?, а на втором этапе по M1 строится эквивалентный ДКА A.

Переработка информации с помощью конечных автоматов

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

Автомат

На такие устройства в последовательные дискретные моменты времени 1,2, …, t, t+1,… поступают входные сигналы x(1),x(2), …, x(t),x(t+1),… и в ответ на них автомат A вырабатывает выходные сигналы y(1) y(2), …, y(t), y(t+1),…. Конечные автоматы характеризуются двумя особенностями.

Отсутствие предвосхищения: выходной сигнал y(t), выдаваемый автоматом в момент t, зависит лишь от полученных к этому времени входов x(1),x(2), …, x(t), т.е. автомат не может предвосхитить будущие входы и заранее на них отреагировать. Таким образом, имеется некоторая функция выходов

(x(1),x(2), …, x(t))= y(t), определяющая очередной выход по предшествующему входу.Конечная память: в каждый момент t информация в автомате о полученном к этому моменту входе x(1),x(2), …, x(t) конечна. Это свойство удобно интерпретировать следующим образом: автомат имеет конечное множество состояний Q и в каждый момент находится в одном из этих состояний. При получении очередного входа состояние может измениться. Таким образом, состояние q Q, в котором находится автомат после получения входной последовательности x(1),x(2), …, x(t), и представляет информацию об этой последовательности, используемую в дальнейшей работе автомата при определении следующего состояния и выхода.

Наше обсуждение приводит к следующему определению конечного автомата с выходом.

Определение 4.1. Конечный автомат - преобразователь - это система вида

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

?X={a1, … , am} (m

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

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

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

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

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

Как автомат A перерабатывает входное слово x1x2 … xt? Он начинает работу в состоянии q(0)=q0. Затем, получив (прочитав) входной символ x1, переходит в состояние q(1)= ?(q0,x1) и выдает символ y(1)= (q0,x1). Далее, получив x2 A переходит в состояние q(2)= ?(q(1),x2) и выдает символ y(2)= (q(1),x2) и т.д. Таким образом, работа автомата, характеризуется последовательностью проходимых им состояний q(0), q(1), … , q(t), … и последовательностью выходных символов y(1), … , y(t), … . Они определяются следующими реккурентными соотношениями:



Рассмотрим несколько примеров автоматов-преобразователей.

Пример 4.1. Сумматор последовательного действия

Мы уже строили схему из функциональных элементов SUMn, реализующую для фиксированного n суммирование двух n-разрядных двоичных чисел. Построим теперь конечный автомат SUM, который сможет складывать два двоичных числа произвольной разрядности. На вход этого автомата будут последовательно подаваться пары x(i)= (x1(i),x2(i)) соответствующих i-ых (1 i r) разрядов двух двоичных чисел x1=x1(r) … x1(2) x1(1) и x2=x2(r) … x2(2) x2(1), а признаком завершения чисел будет служить символ x(r+1)= * (если одно из слагаемых короче другого, то будем считать, что недостающие разряды - нули).


Выходом автомата должна быть последовательность (r+1) двоичных разрядов суммы y = x1 + x2:



Таким образом, входной алфавит автомата: ?X ={ (00), (01), (10), (11), *}, а выходной алфавит: ?Y={ 0, 1}. Что нужно знать автомату SUM о первых i разрядах x1 и x2, чтобы получив их (i+1)-ые разряды (x1(i+1),x2(i+1)), верно определить выход y(i+1)? Ясно, что для этого достаточно знать, был ли перенос в i-ый разряд. Поэтому можно зафиксировать множество состояний Q = {q0, q1}, в котором q0 означает, что переноса не было, а q1 - что перенос был. Теперь легко построить таблицы, представляющие функции переходов и выходов автомата SUM.

?:Q\?X

(00)(01)(10)(11)*?:Q\?X(00)(01)(10)(11)*

q0	q0	q0	q0	q1	q0
q1	q0	q1	q1	q1	q0
q0	0	1	1	0	0
q1	1	0	0	1	1

Заметим, что после получения символа * автомат SUM переходит в начальное состояние q0 и готов выполнять сложение следующей пары чисел.


Рис. 4.1.  Диаграмма автомата SUM

На диаграмме автомата у вершины q0 четыре петли, а у вершины q1 - три, объединены в одну с четырьмя и тремя метками, соответственно. Точно так же слиты два ребра из q1 в q0. Стрелкой указано начальное состояние.

Произведение автоматов

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

Пусть M1 = <?, Q1, q01, F1, ?1> и M2 = <?, Q2, q02, F2, ?2> - два конечных автомата с общим входным алфавитом ?, распознающих языки L1 и L2, соответственно. Определим по ним автомат M= <?, Q, q0, F, ?>, называемый произведением M1 и M2 (M= M1 ? M2), следующим образом. Q= Q1 ? Q2 ={ (q, p) | q

Q1, p Q2}, т.е. состояния нового автомата - это пары, первый элемент которых - состояние первого автомата, а второй - состояние второго автомата. Для каждой такой пары (q,p) и входного символа a ? определим функцию переходов: ?((q,p), a) = (?1(q,a), ?2(p,a)). Начальным состоянием M является пара q0= (q01, q02), состоящая из начальных состояний автоматов-множителей. Что касается множества заключительных состояний, то оно определяется в зависимости от операции над языками L1 и L2, которую должен реализовать M.

Теорема 4.1.

При F

= { (q,p) | q F1 или p F2 } автомат M= <?, Q, q0, F, ?> распознает язык L = L1 L2.При F = { (q,p) | q F1 и p F2 } автомат M= <?, Q, q0, F, ?> распознает язык L = L1 L2.При F\ = { (q,p) | q F1 и p F2 } автомат M= <?, Q, q0, F\, ?> распознает язык L = L1 \ L2.

Доказательство этой теоремы непосредственно выводится из следующего утверждения.

Лемма 4.2. Для любых двух состояний (q,p) и (q', p') автомата M и любого входного слова w слово w переводит (q,p) в (q', p') в автомате M тогда и только тогда, когда оно переводит q в q' в автомате M1 и p в p' в автомате M2.

Лемма устанавливается индукцией по длине слова w.

Следствие4.1.1. Класс конечно автоматных языков замкнут относительно теоретико множественных операций объединения, пересечения и разности.

Автомат по продаже кофе имеет

Задача 4.1. Автомат по продаже кофе имеет щель для получения монет, кнопку, нажатие которой после уплаты достаточной суммы приводит к получению кофе, и накопитель, через который он выдает сдачу покупателю. Автомат принимает монеты достоинством в 1, 2 и 5 рублей. Чашка кофе стоит 8 руб. Пока полученная сумма недостаточна, горит красная лампочка. Если сумма, полученная автоматом, 8, то зажигается зеленая лампочка и после нажатия кнопки автомат наливает кофе и, если требуется, дает сдачу. Если автомат получает монету, когда горит зеленая лампочка, то он немедленно ее возвращает. Определите входной и выходной алфавиты конечного автомата, управляющего продажей кофе, и постройте его функции переходов и выходов.
Задача 4.2. Электронные часы имеют табло с указанием часов, минут и секунд и две управляющие кнопки. Одна кнопка переводит часы из нормального режима в режим настройки времени - вначале в настройку часов, затем - минут, затем - секунд, а затем возвращает в нормальный режим. Другая кнопка в нормальном режиме ничего не меняет, а в режиме настройки нажатие на нее увеличивает на единицу число настраеваемых часов, минут или секунд. Постройте автомат, который принимает на вход сигналы нажатия от двух кнопок, а на выходе выдает сигналы изменения режима и увеличения соответствующего числа.
Задача 4.3. Докажите лемму 4.1 индукцией по длине входного слова.
Задача 4.4. Постройте детерминированные конечные автоматы, которые распознают следующие языки в алфавите ?={a, b}:
L = {w | длина w делится на 5}; L = {w | w не содержит подслов 'aab' и 'bba'}; L = {w | w содержит четное число букв а и нечетное число букв b}; L = {w | число букв а делится на 3, а число букв b на 2 }.
Задача 4.5. Выше в примере 4.1 был построен автомат с выходом, выполняющий сложение двух двоичных чисел. Постройте автомат-распознаватель, который проверяет правильность сложения. На вход поступают последовательности троек нулей и единиц:

Автомат должен допустить такую последовательность, если y = y(n) … y(2)y(1) - это первые n битов суммы двоичных чисел x1= x1(n)… x1(2)x1(1) и x2 = x2(n)… x2(2)x2(1).


Задача 4.7. Докажите лемму 4.2.
Задача 4.8. Докажите, что приведенный на рис. 4.5 автомат A распознает язык, состоящий из всех слов, заканчивающихся на 'aba'.
Задача 4.9. Используя процедуру детерминизации недетерминированных автоматов из теоремы 4.2, постройте ДКА, эквивалентный заданному НКА M.
M=<{a, b},{0, 1,2}, 0,{2}, ?> с программой ?: 0a 1, 0 1, 1b 2, 1 2, 2 b 2. M=<{a, b},{0, 1,2}, 0,{2}, ?> с программой ?: 0a 1, 0a 2, 1b 2, 1 2, 2 b 0.

---

---