Абстрактный синтез конечных автоматов

КОНЕЧНЫЕ АВТОМАТЫ И АВТОМАТНЫЕ ЯЗЫКИ

Абстрактный синтез конечных автоматов

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

Для задания конечного автомата следует определить:

- множество X входных сигналов;

- множество Y выходных сигналов;

- множество Q внутренних состояний;

- одно из множества внутренних состояний как начальное;

- отображение P множества Q × X во множество Q, задающее переходы между внутренними состояниями под воздействиями входных сигналов;

- отображение R множества Q × X во множество Y (модель Мили) или множества Q во множество Y (модель Мура), задающее формирования выходных сигналов в моменты переходов из внутренних состояний под воздействиями входных сигналов (модель Мили) или соответствия выходных сигналов внутренним состояниям (модель Мура).

Компоненты P и R удобно задавать в виде таблиц переходов и выходов или графов переходов и выходов.

Строкам таблицы переходов и выходов ставятся в соответствие элементы множества X входных сигналов, а столбцам – элементы множества Q внутренних состояний. В ячейку таблицы с координатами (x, q), где x Î X, q Î Q, записывается символ v (v Î Q) внутреннего состояния, в которое осуществляется переход из исходного внутреннего q под воздействием входного x, и, в случае модели Мили, - выходной сигнал y (y Î Y), который формируется в момент этого перехода. В случае модели Мура выходные сигналы, так же, как и внутренние состояния, ставятся в соответствие столбцам таблицы.

Пример 1. Описание конечного автомата.

X ={ 0, 1, $ }, Y ={ y, z }, Q ={ A, B, C, D, E }, A – начальное состояние,

таблица переходов и выходов (модель Мура) изображена на рис.1.

Рис.1. Таблица переходов и выходов конечного автомата из примера 1.

Символами «-» в таблице отмечены запрещенные переходы.

На последовательность входных символов 0110$, например, автомат ответит последовательностью выходных символов zzzzy, выполнив, начиная с состояния A, последовательность переходов: A → B → C → D → C → E.

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

Рис. 2. Граф переходов и выходов конечного автомата из примера 1.

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

Так в рассматриваемом примере, если выходной символ y считать признаком принадлежности входной строки языку, принимаемому автоматом, а символ z – признаком противоположного ответа, то о строке 0110$, например, следует сказать, что она является предложением языка, принимаемого автоматом (или короче – является правильной строкой), а о строке 011, например, следует сказать, что она не является правильной строкой с точки зрения автомата. Последовательность переходов автомата под воздействием символов строки 011 заканчивается состоянием D, находясь в котором автомат выдает выходной сигнал z. Такую ситуацию следует рассматривать как одну из обнаруживающих некорректность входной строки. Вторая ситуация, позволяющая считать входную строку неправильной, возникает в случае обнаружения запрета перехода из текущего внутреннего состояния под воздействием текущего символа входной строки. По этой причине, например, строку 0111 следует признать неправильной, так как заключительный переход из состояния D под воздействием последнего символа 1 входной строки оказывается запрещенным. В целом же, о языке, принимаемом этим автоматом, можно сказать, что он представляет собой бесконечное множество строк, составленных из пар символов 01 и/или 10, заканчивающихся символом $.

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

Регулярные выражения используются для описания регулярных множеств. Любое множество строк, которое можно получить из символов заданного конечного алфавита с помощью операций объединения (дизъюнкции), конкатенации и итерации, называется регулярным множеством [2]. Уточним, что множество, полученное конкатенацией двух множеств строк, состоит из строк, полученных попарной конкатенацией строк-элементов исходных множеств, а итерация множества строк – это ноль и более конкатенаций этого множества с самим собой (ноль конкатенаций дает пустую строку). Соответственно, в записи регулярных выражений используются именно эти операции. Условимся в записи регулярных выражений знак операции конкатенации опускать, операцию объединения обозначать символом , а операцию итерации – скобками {}, выделяя их жирным шрифтом, чтобы отличать от аналогичных скобок в обозначении множества. Следует иметь в виду также, что операция конкатенации имеет более высокий приоритет, чем операция объединения, а операция итерации – более высокий, чем операция конкатенации. Для повышения приоритета операции можно использовать круглые скобки ().

Так, скажем, для символов алфавита { a, b, c, d } примерами регулярных выражений и соответствующих им регулярных множеств могут быть:

Регулярное выражение	Регулярное множество	Комментарии
a	{ a }
ab	{ ab }	применена операция конкатенации
ab cd	{ ab, cd }	применены операции конкатенации и объединения
{ ab }	{ Λ, ab, abab, ababab,… }	применены операции конкатенации и итерации (Λ – обозначение пустой строки)

Любые регулярные выражения и только они представимы в конечных автоматах [1]. Поэтому формальные языки, распознаваемые (принимаемые) конечными автоматами, являясь регулярными множествами, могут описываться регулярными выражениями.

Приведем еще несколько примеров описания регулярных множеств (языков).

{ a b c d } - множество всех строк (слов) в алфавите { a, b, c, d } или пустая строка;

{ a b c d } c - множество всех слов в алфавите { a, b, c, d }, заканчивающихся буквой c;

(a b c d)(a b c d) – множество всех двухбуквенных слов в алфавите { a, b, c, d }.

Если формальный язык удалось описать регулярными выражениями, то построение конечного автомата для последующей программной реализации распознавателя такого языка можно считать делом техники при использовании, например, алгоритма, изложенного в [1]. В основу алгоритма положена идея разметки регулярных выражений символами внутренних состояний автомата. Местами регулярных выражений, которые отмечаются символами внутренних состояний, считаются позиции между любыми рядом стоящими символами, в том числе – между символами алфавита языка, знаками операций и скобками, а также – позиции перед первым символом и после последнего символа регулярного выражения. Места регулярного выражения, вообще говоря, могут отмечаться несколькими символами внутренних состояний.

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

|(| 0 | 1 | | 1 | 0 |)| $ |

0 0 1 2 0 3 4 2 5

Места регулярного выражения обозначены символом |. В качестве символов внутренних состояний автомата здесь используются неотрицательные числа. Числом 0 обозначено начальное состояние будущего автомата. Конечное место регулярного выражения отмечено символом внутреннего состояния (5), в котором автомат сформирует выходной сигнал-признак принадлежности входной строки языку, принимаемому автоматом (описанному регулярным выражением). Рассматриваемый алгоритм предполагает построение автомата Мура.

Два символа внутренних состояний, оказавшиеся метками мест, расположенных в регулярном выражении по разные стороны от символа алфавита языка, указывают на возможность перехода автомата между этими внутренними состояниями. При этом исходным состоянием является то, метка которого размещена слева от символа языка, а состоянием перехода – то, метка которого размещена справа от символа языка, а сам символ – это входное воздействие, которое инициирует такой переход. Так, в частности, из приведенного примера размеченного регулярного выражения следует, что для соответствующего автомата определен переход из внутреннего состояния 3 во внутреннее состояние 4 под воздействием входного символа 0, поскольку позиция слева от символа 0 отмечена меткой внутреннего состояния 3, а справа – меткой 4. Полностью поведение автомата, построенного по этому регулярному выражению, можно изобразить таблицей переходов и выходов, представленной на рис. 3.

Рис. 3. Таблица переходов и выходов конечного автомата из примера 2.

Выходные символы приписаны внутренним состояниям автомата в предположении, что признаком принадлежности строки входных символов языку, принимаемому автоматом, является выходной символ y, а на все остальные строки входных символов автомат отвечает выходом z.

В полученной таблице два столбца оказались одинаковыми по содержанию. Это столбцы, озаглавленные символами внутренних состояний 2 и 4. Такие внутренние состояния можно считать эквивалентными и объединить их в одно состояние. Обозначим объединенное состояние, например, символом 2. Получим таблицу меньшего размера (рис. 4).

Рис. 4. Таблица переходов и выходов конечного автомата из примера 2 после минимизации

В общем случае эквивалентными, а значит – подлежащими объединению, считаются такие внутренние состояния, начиная с которых, автомат на одинаковые последовательности входных символов формирует одинаковые последовательности выходных символов. Чтобы найти эквивалентные состояния в таблице переходов и выходов, следует сравнить столбцы переходов из состояний, отмеченных одинаковыми выходными символами. Для эквивалентности таких состояний необходимо, чтобы переходы из них под воздействиями одноименных входных символов были одинаковыми или, в более общем случае, - эквивалентными.

Язык, который описан размеченным регулярным выражением и принимается построенным автоматом, – это множество из двух строк: { 01$, 10$ }. Последовательность символов каждой из этих двух строк переводит автомат из начального состояния 0 в заключительное состояние 5, попав в которое автомат формирует выходной символ y, признак правильности входной строки.

Заметим, что таблица переходов и выходов построенного автомата похожа на таблицу переходов и выходов из примера 1. В отличие от примера 2, язык, из примера 1 является бесконечным множеством строк, составленных из пар символов 01 и/или 10, заканчивающихся символом $. Регулярное выражение, описывающее такой язык, должно содержать итерацию:

(01 10) { 01 10 } $. (1)

Или:

{ 01 10 } (01 10) $. (2)

Ограничиться только выражением { 01 10 } в данном случае нельзя, поскольку результатом итерации может быть пустая строка, которая не принадлежит языку из примера 1. Таблицы переходов и выходов для двух последних выражений получаются идентичными, несмотря на различия в разметке.

Общие правила разметки регулярных выражений, сформулированные в [1], сводятся к следующему.

1. Индекс места перед любыми скобками распространяется на начальные места всех дизъюнктивных членов, записанных в этих скобках.

2. Индекс конечного места любого дизъюнктивного члена, заключенного в любые скобки, распространяется на место, непосредственно следующее за этими скобками.

3. Индекс места перед итерационными скобками распространяется на место, непосредственно следующее за этими скобками, а индекс места за итерационными скобками – на начальные места всех дизъюнктивных членов, заключенных в итерационные скобки.

4. Индекс конечного места любого дизъюнктивного члена, заключенного в итерационные скобки, распространяется на начальные места всех дизъюнктивных членов, заключенных в эти итерационные скобки.

5. Индексы мест, слева и справа от которых стоят буквы, никуда не распространяются.

6. Индекс конечного места распространяется на те же места, на которые распространяется индекс начального места. Это правило справедливо только в тех случаях, когда предполагается построение автомата многократного действия, т.е. автомата, принимающего последовательность строк, описанных регулярным выражением.

Очевидно, что разметка регулярного выражения из примера 2 соответствует этим правилам. Выполним теперь, руководствуясь этими правилами, разметку регулярного выражения (1) с итерационными скобками. При этом в качестве меток-индексов возьмем, для разнообразия, буквы латинского алфавита. В данном примере это имеет смысл сделать еще и для того, чтобы символы разметки не совпадали с символами входного алфавита (это замечание справедливо и по отношению к разметке в примере 2).

|(| 0 | 1 | | 1 | 0 |)| { | 0 | 1 | | 1 | 0 | } | $ |

_{A A B C A D F C C G H C I J C E}

_{F F F F}

_{H H H}

_{J J J}

По размеченному регулярному выражению, с учетом прежней договоренности о выходных символах y и z, может быть построена таблица переходов и выходов автомата. Она представлена на рис. 5.

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

После объединения эквивалентных состояний C, F, H и J под именем C таблица примет вид, изображенный на рис.6.

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

В преобразованной таблице более очевидной становится эквивалентность состояний B и G (объединим их под именем B), а также – состояний D и I (объединим их под именем D). Результат этих преобразований – таблица переходов и выходов из примера 1.

Разметка регулярного выражения (2), описывающего тот же язык, и соответствующая таблица переходов и выходов выглядят более громоздкими. Но после минимизации, естественно, получается всё тот же автомат из примера 1. Заметим, что процедура построения автомата по регулярному выражению (2) имеет некоторые особенности. Выполним разметку регулярного выражения:

| { | 0 | 1 | | 1 | 0 | } | (| 0 | 1 | | 1 | 0 |) | $ |

_{A A B C A D F C C G H C I J H E}

_{C A C A F F F J}

_{F F F C A A A}

При построении таблицы переходов с использованием такой разметки может возникнуть впечатление недетерминированности поведения автомата в некоторых ситуациях. Так, например, в соответствии с разметкой, из состояния A под воздействием входного символа 0 автомат может перейти как в состояние B, так и в состояние G. Для того, чтобы получить детерминированный автомат, в такой неопределенной ситуации следует ввести новое внутреннее состояние, в которое он должен перейти. В случае упомянутого перехода из A под воздействием входного символа 0, обозначим это новое состояние сложным именем: B G. Сложное имя несет на себе смысловую нагрузку, подсказывая, как должны быть определены переходы из нового внутреннего состояния. А именно – объединением одноименных (под воздействием одних и тех же входных символов) переходов из состояний B и G. Использование этого приема позволяет получить таблицу переходов и выходов, изображенную на рис. 7.

A

B

C

D

E

F

G

H

I

J

B G

D I

C H

F J

0

B G

-

B G

F

-

B G

-

-

J

-

-

F J

B G

B G

1

D I

C

D I

-

-

D I

H

-

-

-

C H

-

D I

D I

$

-

-

-

-

-

-

-

E

-

E

-

-

E

E

z

z

z

z

y

z

z

z

z

z

z

z

z

z

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

Из полученной таблицы можно удалить столбцы B, G, D, I, поскольку в соответствующие состояния нет переходов. Затем могут быть удалены и столбцы C, H и J в связи с исчезновением переходов в состояния с такими именами.

Дальнейшее упрощение таблицы выполняется объединением эквивалентных состояний: A и F объединим под именем A; C H и F J объединим под именем C. Кроме того, упростим длинные имена: B G переименуем в B, а D I переименуем в D. После всех этих преобразований снова получается таблица переходов и выходов из примера 1.

Если конечной целью всех манипуляций с регулярными выражениями и соответствующими им конечными автоматами является программная реализация распознавателя автоматного языка, можно воспользоваться программными средствами, облегчающими процесс достижения этой цели. Одним из таких средств является утилита Flex. Принимая на входе описание автоматного языка в виде регулярного выражения, она формирует на выходе программную реализацию конечного автомата, принимающего этот язык. Программная реализация конечного автомата оформлена в виде C-функции int yylex().

Следует иметь в виду, что правила написания регулярных выражений для Flex несколько отличаются от тех, что были рассмотрены выше. Операция объединения обозначается символом |, а операция итерации – символом *, который помещается справа от операнда. Как и ранее, знак конкатенации опускается, а для повышения приоритета операции используются круглые скобки.

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

(01 | 10)(01 | 10)*

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

Так, выбор одного из символов некоторого множества можно обозначить скобками []. И поэтому, например, регулярное выражение a b c d во входном языке Flex можно записать в виде [ abcd ] или даже - [ a-d ], поскольку множество внутри квадратных скобок разрешается представить диапазоном символов.

Еще одним полезным дополнительным средством, предлагаемым Flex, является возможность именовать регулярные выражения и пользоваться такими именами при составлении более сложных регулярных выражений, в частности, вместо того, чтобы повторять запись многократно входящих в состав выражения некоторых подвыражений. Так, например, если выражение 01 10 поименовать идентификатором Rname, что на языке Flex выглядело бы как Rname 01|10, то регулярное выражение (01 10) { 01 10 } $ можно записать в виде: {Rname}{Rname}*$. Фигурные скобки в этой записи используются для указания на использование регулярного выражения, ранее поименованного.

Более детально правила оформления входного файла для Flex изложены в [3]. Не комментируя здесь эти детали, приведем полностью содержание файла, позволяющего с помощью Flex реализовать автоматный распознаватель языка, который состоит из бесконечного множества строк, составленных из пар символов 01 или 10, заканчивающихся символом $:

%option noyywrap

%option never-interactive

%{

#include <iostream>

using namespace std;

%}

Rname 01|10

String {Rname}{Rname}*\$

%%

{String} {return 1;}

%%

void main()

{yyin=fopen("infile.txt","r");

while(yylex()>0)cout<< "correct string\n";

}

Программой предусмотрено чтение строк для анализа из файла infile.txt, а после каждой успешно распознанной строки – возвращение функцией yylex константы 1 (оператор return 1) и вывод сообщения «correct string» функцией main.

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

Для задания формальной грамматики следует определить:

- множество T ее терминальных символов (алфавит языка),

- множество V ее нетерминальных (вспомогательных) символов,

- множество P порождающих правил,

- начальный символ, или аксиома, S (S Î V).

Для описания компоненты P, в свою очередь, нужен формальный язык. В качестве такого мета-языка (языка описания языка) будем использовать форму Бэкуса-Наура [5]. У этого мета-языка есть свои символы – мета-символы:

::= - символ, делящий правило на левую и правую части, на определяемое и определение, соответственно;

<> - скобки для выделения имени нетерминального символа;

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

Язык из примера 1 можно представить следующей грамматикой:

T ={ 0, 1, $ },

V ={< B >,< C >,< D >,< E >},

множество P порождающих правил:

< E >::=< C > $

< C >::=< B > 1| < D > 0

< D >::=< C > 1|1

< B >::=< C > 0|0

< E > - аксиома (компонента S).

С помощью порождающих правил из аксиомы грамматики можно породить (вывести) любое предложение языка, который описывается этой грамматикой. В том числе, например, – строку 0110$: < E > => < C > $ => < D > 0$ => < C > 10$ => < B > 110$ => 0110$. На каждом шаге вывода, обозначенном символом =>, нетерминальный символ заменялся правой частью одного из правил, в которых он находится в левой части. Все цепочки символов, терминальных и (или) нетерминальных, в том числе – аксиома и предложение языка, называются сентенциальными формами.

Задача определения того, является ли заданная строка предложением языка, который описывается заданной грамматикой, называется задачей разбора. Для решения этой задачи нужно попытаться вывести из аксиомы заданную строку. Или наоборот: попытаться свернуть заданную строку к аксиоме за несколько шагов, заменяя на каждом шаге фрагмент сентенциальной формы на нетерминальный символ согласно правилам грамматики.

Представление о таком сворачивании дает чтение приведенного выше вывода строки 0110$ справа налево. Заметим, что последовательность нетерминальных символов (нетерминалов): < B >,< C >,< D >,< C >,< E >; - при прочтении вывода справа налево практически совпадает с последовательностью смены внутренних состояний конечным автоматом из примера 1 при распознавании той же строки. Последовательность нетерминалов отличается от последовательности внутренних состояний только отсутствием символа < A >. Совпадение этих двух последовательностей не является случайным. Процедура распознавания предложения языка с помощью конечного автомата является обратной по отношению к процедуре вывода этого предложения из аксиомы автоматной грамматики.

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

1) множество X входных сигналов автомата совпадает со множеством T терминальных символов грамматики;

2) множество Q внутренних состояний автомата определяется множеством V нетерминальных символов грамматики;

3) переходы между внутренними состояниями автомата под воздействиями входных сигналов определяются порождающими правилами грамматики: правило вида < U >::=< W > x (x Î T) соответствует в автомате переходу из состояния W в состояние U под воздействием входного сигнала x, а правило вида < U >::= x соответствует в автомате переходу из начального состояния в состояние U под воздействием входного сигнала x;

4) выходным сигналом, являющимся признаком принадлежности строки языку, принимаемому автоматом, отмечается внутреннее состояние автомата, соответствующее аксиоме грамматики.

Начальному состоянию автомата, судя по приведенным правилам построения автомата, может не соответствовать никакой нетерминальный символ грамматики, что действительно имеет место в рассматриваемом примере: A – начальное внутреннее состояние автомата, а в грамматике нет терминального символа < A >.

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