Конечные автоматы

13. Конечные автоматы

В этом параграфе строятся некоторые абстрактные вычислительные устройства (автоматы), которые в некотором естественном смысле по своим возможностям равносильны регулярным грамматикам. С точки зрения построения транслятора полезность автоматов будет заключаться в следующем. Грамматика – удобное средство описания языка. Но в силу присущей ей декларативности она не слишком удобна для прямого перевода на язык программирования, на котором мы пишем, допустим, лексический анализатор. Автомат же, напротив, имеет ярко выраженный процедурный характер. Поэтому программировать действия автомата можно чуть ли не автоматически.

Конечным автоматом называется объект

A = < Q,T,d,S,F>

где:

Q,T – конечные непересекающиеся множества,

d:Q ´T® P(Q) –функция,

S Î Q,

F Í Q.

Здесь:

Q´T – множество упорядоченных пар <q,t>, где qÎQ, tÎT (прямое или декартово произведение множеств);

P (Q) - множество всех подмножеств множества Q;

Функция d:X ® Y – это правило, сопоставляющее каждому элементу xÎX один элемент d(x)ÎY.

Множество Q называется множеством состояний. При этом элемент SÎQ называется начальным состоянием, а элементы из F называются заключительными состояниями.

Функция d - это функция переходов. Тот факт, что p Î d (q,t) мы трактуем как высказывание:

”автомат A из состояния q, получив символ t, может перейти в состояние p”.

Символы алфавита T назовем терминальными. Их роль будет согласована с ролью терминалов в формальных грамматиках. Состояния подобны нетерминалам, но имеются тонкости.

Опишем работу автомата более точно.

1.  Автомат осуществляет свою работу по шагам или тактам.

2.  На каждом шаге он находится в одном из своих состояний (допустим q Î Q).

3.  Состояние S называется стартовым. С него начинается работа.

4.  Перед каждым шагом “на входе” автомата имеется какое-то слово a алфавита T (обрабатваемое слово). Шаг определен, если слово a - не пустое (a¹e) и, одновременно, множество d (q, а) – не пустое (d (q, а) ¹ Æ), где а – первая буква слова a.

5.  Пусть a¹e, d (q, а) ¹ Æ и a представимо в виде a = аb. При этом говорим, что символ а – первая буква слова a - воспринимается (обрабатывается) автоматом A на рассматриваемом шаге.

6.  В результате выполнения одного шага автомат из состояния q переходит в одно из состояний p Î d (q, а). После этого на входе он имеет слово b.

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

< q , a>

что произносится как:

“Автомат A в состоянии q имеет на входе слово a”

Описанный выше один шаг работы автомата изобразим в виде

< q, a>Þ< p , b >

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

< S , a> = < q1 , b1>Þ< q2 , b2 >Þ …Þ < qk , bk > = < D,e >

где D – одно из заключительных состояний.

Слово “возможно” в этом определении говорит о том, что работа автомата, имеющего на входе слово a, может и не завершиться так удачно, как требуется. На каждом шаге переход к следующему состоянию осуществляется, вообще говоря, неоднозначно. Автомат может перейти в любое из состояний p Î d (q, а). Утверждение “a воспринимается” означает, что возможен такой выбор по ходу вычисления, когда цепочка a заканчивается и как раз в этот момент автомат переходит в одно из заключительных состояний.

В ходе вычисления автомат может несколько раз побывать в заключительных состояниях. Переход в такое состояние не означает остановки. Сигналом к остановке является пустая цепочка на входе. При удачном вычислении автомат в момент, когда обрабатываемая цепочка заканчивается, должен оказаться в каком-то заключительном состоянии.

Множество всех цепочек, воспринимаемых автоматом A, называется языком, определяемым этим автоматом, и обозначается как L(A). Некое множество слов алфавита T называется автоматным языком, если оно совпадает с L(A) для некоторого автомата A.

Автомат удобно изображать в виде графа, вершины которого помечены символами состояний (являются состояниями). Из одних состояний в другие проведены стрелки, помеченные терминальными символами.

Наличие стрелки

означает, что p Î d (q, а).

Заключительные состояния изображаются в виде двойных кружков

Стартовое состояние помечается указывающей на него стрелочкой.

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

Пример. Конечный автомат, распознающий правильные e-mail-адреса.

Теорема. Язык тогда и только тогда является автоматным, когда он регулярен.

Доказательство. По любой регулярной грамматике G построим некий автомат A = A (G). Для начала проделаем с грамматикой G процедуру освобождения от e–правил. Далее автомат A (G) по G строится очень просто. Множество терминалов T у A и у G общее. Состояния автомата - это нетерминалы G, но к ним добавим еще одно состояние E, которое сделаем заключительным. Состояние S становится, естественно, стартовым состоянием автомата.

Для всякого правила грамматики A®a из состояния A проводим стрелку в состояние E и помечаем ее символом a. Для всякого правила грамматики A®aB из состояния A проводим стрелку в состояние B и помечаем ее символом a. Если в G есть e–правило S®e, то состояние S делаем заключительным.

Докажем, что L(G) = L(A). Рассмотрим какое-нибудь терминальное слово a. Для примера предположим, что

a = abcd

Пусть aÎ L(G). Вывод этой цепочки можно представить в виде

S Þ aA Þ abBÞ abcC Þ abcd

что говорит о том, что грамматика содержит продукции S® aA, A® bB, B® cC, C® d. Стало быть автомат содержит переходы:

, ,,.

Теперь очевидно, что построенный автомат воспринимает цепочку abcd. То, что показано на примере этой цепочки обобщается, понятно, на любой случай выводимости в G любого непустого слова. Если же e Î L(G), то среди правил G есть S®e, и, значит, состояние S автомата является заключительным, что говорит о том, что A воспринимает пустую цепочку. Таким образом aÎL(A).

Пусть, наоборот, aÎL(A). Тогда имеется последовательность конфигураций автомата:

< S, abcd> Þ < A, bcd> Þ < B, cd > Þ < C, d> Þ < D,e>

для некоторых состояний автомата A,B,C,D, причем D является заключительным состоянием, т. е. D=E или D=S. При D=E автомат содержит переходы:

, ,,.

Эти переходы могут быть в A только из-за существования в G продукций

S® aA, A® bB, B® cC, C® d.

А из этих правил получаем вывод слова abcd в G. При D=S в G существуют продукции S® aA, A® bB, B® cC, C® dS и S®e (как бы иначе S могло стать заключительным?). Из этих правил также получается вывод abcd. Наконец, если слово a пустое и допускается автоматом, то S – заключительное состояние и в G имеется правило S®e благодаря которому e выводится из G. Таким образом aÎL(G). Следовательно L(A) = L(G)..

Теперь определим обратную конструкцию, которая по автомату A=<Q,T,d,S,F> определяет некую грамматику G = G(A). Нетерминалами грамматики являются состояния автомата. Начальным нетерминалом грамматики является начальное состояние автомата. Терминалы у G и у A общие.

Для каждых A Î d(B,a) в грамматику добавляем правило B®aA. Если A – заключительное состояние автомата, в грамматику добавляем e–правило A ®e.

Опять надо доказать, что L(G) = L(A). Как прежде берем какое-нибудь терминальное слово a. Для примера предположим, что

a = abcd

Пусть aÎ L(G). Вывод этой цепочки можно представить в виде

S Þ aA Þ abBÞ abcC Þ abcd

или в виде

S Þ aA Þ abBÞ abcC Þ abcdD Þ abcd

Это говорит о том, что грамматика содержит продукции S® aA, A® bB, B® cC, C® dD и D®e. Стало быть D – заключительное состояние автомата и он содержит переходы:

, ,,.

Видим, что автомат воспринимает цепочку abcd. Если цепочка a пустая, то eÎ L(G) означает, что S®e - правило G. Отсюда S – заключительное состояние автомата. Значит автомат воспринимает e. В любом случае aÎL(A).

Пусть, обратно, aÎL(A). Тогда имеется последовательность конфигураций автомата:

< S, abcd> Þ < A, bcd> Þ < B, cd> Þ < C, d> Þ < D,e>

для некоторых состояний автомата A,B,C,D, причем D является заключительным состоянием. Значит автомат имеет переходы:

, ,,.

а G содержит продукции:

S® aA, A® bB, B® cC, C® dD, D®e.

Из этих правил получаем вывод слова abcd в G. Случай пустого a также легко рассматривается. Значит aÎL(G). Следовательно L(G) = L(A).

Таким образом доказано, что любой регулярный язык является автоматным и наоборот. Теорема доказана.

Заметим, что доказательство содержит алгоритмы переделки регулярной грамматики в конечный автомат, а конечного автомата – в регулярную грамматику. А это имеет уже практические применения.