Детерминированные и недетерминированные конечные автоматы

Конфигурация конечного автомата - это элемент множества Q´å^*, т.е. последовательность вида qw, где q - состояние из Q, w - элемент из å^*.

Если к любой конфигурации q_iw применимо не более одного правила, то такой автомат называется детерминированным конечным автоматом (ДКА). В противном случае мы имеем дело с недетерминированным конечным автоматом (НКА).

Итак, недетерминированные конечные автоматы отличаются от ДКА

(5) неоднозначностью переходов;

(6) наличием, в общем случае, более чем одного начальных состояний.

КА удобно представлять в виде диаграммы состояний (переходов), представляющей собой ориентированный граф.

 

Пример 1. Пусть задан следующий НКА

КА = (å,Q,q₀,T,P)

å = {0,1},

Q = {S,A,B,q_f},

q₀ = S,

T = {q_f},

P = {S0®q_f, S0®A, A1®B, B0®q_f, B0®A}

 

Диаграмма его переходов будет выглядеть так:

Пример 2. Рассмотрим понятие идентификатора, представленное в НФБ и в виде ДКА:

<идент>::= <бкв>

<идент>::= <идент><бкв>

<идент>::= <идент><цфр>

<бкв>::= a|b|...|z

<цфр>::= 0|1|...|9

Изобразим множество P в виде матрицы (т.н. матрицы переходов)

P:

	1	2	3
<бкв>	2	2	-
<цфр>	4	2	-
<конец>	4	3	-
<иначе>	4	-	-

Строки матрицы – входные символы, столбцы – состояния автомата. Некоторые элементы этой матрицы – явно лишние. В частности, 3-й столбец вовсе не нужен. Эти "лишние" состояния могут служить для диагностики ошибок.

 

Обобщенный алгоритм работы этого автомата может быть реализован на языке С следующим образом:

 

char c;       //текущий исходный символ

int q;          //номер состояния

int a;          //входной текущий символ для автомата

q=0;           //начальное состояние автомата

while(1)     //бесконечный цикл

{      c = readchar();     //считывание входного символа

a = gettype(c);      //распознавание входного символа –

                                           //отнесение его к одной из известных автомату

                                           //категорий - <бкв>, <цфр>, <конец> или <иначе>

//Выполнение перехода

q = P[a, q];

//Обработка

if (q==3) return 1; //нормальный выход из программы

if (q==4) return 0; //выход по ошибке

}

 

Обратите внимание на то, что входной алфавит – это то, что автомат умеет воспринимать. При этом он не обязан различать между собой, скажем, буквы и цифры.

 

Пример 3. Арифметическое выражение (без скобок)

<expr>::= <число>|<идент>

<expr>::= <expr><op><expr>

<op>::= +|-|*|/

<число>::= <цфр>

<число>::= <число><цфр>

 

Рассмотрим анализатор языка, распознаваемый КА, структура которого приведена ниже:

 

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

 

/*

АНАЛИЗАТОР РЕГУЛЯРНОЙ ГРАММАТИКИ - 1

S->1S

S->1B

S->0A

A->0A

A->0B

B->1S

Начальное состояние S

Конечное состояние B

*/

 

goal

Recognize([1,1,1,1,1,0,0,0,0,0,0,1,1,0,0,0,0]).

clauses

Recognize(L):- s(L), write("ФРАЗА РАСПОЗНАНА").

Recognize(_):- write("*** ОШИБКА! ФРАЗА НЕ РАСПОЗНАНА").

 

append([],L,L).

append([H|T],B,[H|C]):- append(T,B,C).

 

S(L):- append(L1,L2,L), L1=[1], S(L2).

S(L):- append(L1,L2,L), L1=[1], B(L2).

S(L):- append(L1,L2,L), L1=[0], A(L2).

A(L):- append(L1,L2,L), L1=[0], A(L2).

A(L):- append(L1,L2,L), L1=[0], B(L2).

B(L):- append(L1,L2,L), L1=[1], S(L2).

B([]).

 

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

 

/* АНАЛИЗАТОР РЕГУЛЯРНОЙ ГРАММАТИКИ – 2. Вариант без предиката append */

goal

Recognize([1,1,1,1,1,0,0,0,0,0,0,1,1,0,0,0,0]).

clauses

Recognize(L):- s(L), write("ФРАЗА РАСПОЗНАНА").

Recognize(_):- write("*** ОШИБКА! ФРАЗА НЕ РАСПОЗНАНА").

S([1|L]):- S(L).

S([1|L]):- B(L).

S([0|L]):- A(L).

A([0|L]):- A(L).

A([0|L]):- B(L).

B([1|L]):- S(L).

B([]).

 

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

Реализовать недетерминированный автомат на Прологе достаточно просто. А сделать то же самое на процедурном языке – задача весьма нетривиальная. На практике поэтому предпочтительнее работать с "нормальным", детерминированным автоматом, не допускающим неоднозначностей.

ПОСТРОЕНИЕ ДКА ПО НКА

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

Для любого НКА можно построить эквивалентный ему конечный детерминированный автомат.

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

Теорема. Пусть НКА F= (å,Q,q₀,T,P) допускает множество цепочек L. Определим ДКА F'= (å',Q',q₀',T',P') следующим образом:

Множество состояний Q' состоит из всех подмножеств множества Q. Обозначим элемент множества Q' через [S₁,S₂,..,S_l], где S₁,S₂,..,S_lÎQ.

å' = å.

Отображение P' определяется как

P'([S₁,S₂,..,S_m],x) = [R₁,R₂,..,R_m],

где P({S₁,S₂,..,S_m },x) = { R₁,R₂,..,R_m }, S_i,R_iÎQ, xÎå.

Пусть q₀={S₁,S₂,..,S_k}.

Тогда q₀'=[S₁,S₂,..,S_k].

Пусть множество заключительных состояний T={S_j, S_k,.., S_n}.

Тогда T'=[S_j, S_k,.., S_n].

Или, иначе,

T'={t=[S_a,S_b,..,S_c] | $ S_b: S_bÎT}.

Построенный таким образом детерминированный конечный автомат будет эквивалентен в смысле "вход-выход" исходному НКА.

 

Приведем пример построения ДКА по НКА. Пусть дан недетерминированный автомат

Правила переходов: {S1®S, S1®Z, S0®P, P1®Z, P0®Z, Z1®P, Z1®S}.

Начальные состояния: {S, P}.

Заключительные состояния: {Z}.

 

Множество состояний ДКА будет таким: {S, P, Z, PS, SZ, PSZ, PZ}. Их будет ровно 2ⁿ-1, где n – количество состояний исходного автомата.

Его правила переходов:

{S1®SZ, S0®P, P1®Z, P0®Z, Z1®PS, PS1®SZ, PS0®PZ, SZ1®PSZ, PSZ1®PSZ, PZ1®PSZ}.

Начальное состояние: SP.

Заключительные состояния: {Z, PZ, SZ, PSZ}.

Тогда детерминированный автомат будет выглядеть так:

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

Завершая рассуждения о недетерминированных автоматах, следует отметить еще один момент, связанный с множеством начальных состояний (н.с.) в НКА. Дело в том, что когда имеется несколько н.с., работа автомата заключается в том, что переход по входному символу осуществляется одновременно из всех начальных состояний. Именно в этом заключается суть процедуры объединения всех н.с. в одно. Это особенно важно при моделировании НКА, скажем, средствами Пролога.

ПРОГРАММИРОВАНИЕ СКАНЕРА

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

(7) разделители или операторы (+,-,*,/,(,) и т.п.);

(8) служебные слова (что-то вроде begin, end,... и т.п.);

(9) идентификаторы;

(10) числа.

Кроме того, необходимо исключать комментарии (как строчные, типа '//', так и многострочные, вида '/*...*/').

Строить сканер мы будем, используя конечный автомат. К автомату предъявляются следующие минимальные требования:

Автомат должен формировать поток лексем;

Автомат должен заносить полученные лексемы в таблицу символов или имен.

 

Наш распознающий автомат упрощенно может выглядеть следующим образом:

Здесь под символом D понимается цифра, L означает букву, а delim – разделитель (пробел, табуляцию и т.п.). Состояние int отвечает за распознавание числа, id – за распознавание имени, а sla, com, end и R – за распознавание комментариев. Чтобы не загромождать схему дугами, переходы в основное состояние S обозначены дублированием этой вершины.

При этом следует отметить, что

При переходе в начальное состояние S иногда требуется возвращать обратно считываемый символ входной последовательности, т.е. необходимо сместить указатель на одну позицию назад. Иначе мы просто будем терять часть лексем, т.к. автомат -–это устройство, последовательно считывающее очередной входной символ на каждом такте работы.

Автомат в таком виде бесполезен, он не выполняет никаких полезных процедур.

 

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