2.4. Автоматы и грамматики [ 7 ]

Автомат распознаёт цепочку  над V , если, находясь в начальном состоянии, автомат получает на вход цепочку  последовательно символ за символом, и после завершения цепочки оказывается в выделенном состоянии w₀ . Для построения автомата, распознающего язык, порождаемый А-грамматикой G, необходимо каждому вспомогательному символу wW поставить в соответствие состояние автомата, в качестве множества терминальных символов взять множество входных символов автомата, каждому правилу w::vw¹ поставить в соответствие переход между состояниями w и w¹ под воздействием входного символа v. Начальному состоянию автомата соответствует w₁ ,а выделенному состоянию w₀ .

В рассматриваемом примере построим граф автомата (Рис. 12).

Рис.12

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

В рассматриваемом примере это :

У₁) S:=d

У₂) S:=2*S=d

У₃) M:=1

У₄) M:=M/2; S:=S+d*M

У₅) выдача числа S

У₆) сообщение о синтаксической ошибке

Структура автомата, который можно назвать интерпретирующим, приведена на Рис. 13.

Рис. 13

Правила А-грамматики можно записать в виде:

w_i ::v_j w_k (jJ_i, kK_ij, iI),

причём w_k WU{ w₀ }, где w₀ – пустой символ.

Если существует | K_ij |>1, то автомат, построенный по грамматике G с помощью изложенной выше процедуры, будет недетерминированным.

Например, системе правил

w₁ :: v₁ w₂ | v₂ w₃

w₂ :: v₂ | v₂ w₂

w₃ :: v₃ | v₃ w₃

соответствует недетерминированный автомат, граф которого показан на рис. 14.

Рис.14

Для построения детерминированного автомата преобразуем недетерминированный автомат путём введения новых состояний и правил на основе следующих соотношений

w₁ :: = v_j { w_k | kK_1j };

{w_i | iM} :: = v_j { w_k | k K_ij ,iM} (iUJ_i ),

где множество вида { w_t | tT} соответствует новым состояниям.

В рассматриваемом примере получим

J₁ = {1} , J₂ = {2}, J₃ ={3};

K₁₁ ={2,3}, K₂₂ ={0,2}, K₃₃ = {0,3};

w₁ ::=v₁ {w₂ , w₃ }

{w₂ , w₃ } ::=v₂ {w₀ , w₂ } | v₃ {w₀ , w₃ };

{w₀ , w₂ } ::=v₂ {w₀ , w₂ };

{w₀ , w₃ } ::=v₃ {w₀ , w₃ }.

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

Рис.15

Выделенными состояниями являются {w₀ , w₂ } и {w₀ , w₃ }.

Завершение работы автомата в этих состояниях означает распознование цепочки языка.

В заключении приведён пример бесконтекстной грамматики, не являющейся автоматной. Эта грамматика, распознающая правильные скобочные выражения, имеет правила

w₁::={w₂ , w₃ }; w₂ ::=(w₂) | w₀ ; w₃ ::=w₂ | w_{0 ,}

_где w₁ – начальный символ

w₀ - пустой символ

( , ) - терминальные символы.

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

Рис. 16

Состояние является одновременно и начальным и выделенным заключительным состоянием. Распознавание цепочки ( ( ( ( ( ( ( (

^{1 2 3 4 5 6 7 8}

показано на рис. 17

Рис. 17