Формальные языки


Построение магазинного автомата



 

Утверждение. Если Г = { Vт

, Va , I , R } является КС-грамматикой, то по ней можно построить такой магазинный автомат М, что L(M) = L(Г).

 
В основе доказательства лежит способ построения магазинного автомата по  заданной КС-грамматике.Чтобы сделать процесс построения автомата более простым и наглядным, условимся использовать магазинные автоматы с одним состоянием s0.  Итак, пусть задана грамматика  Г = { Vт , Va , I , R }. Определим компоненты автомата М следующим образом:

    S = { s0 },     P = Vт ,     H = VтИ  VaИ  { h0} ,      F = {  s0 },

в качестве начального состояния автомата примем s0 и построим функцию переходов так:
               1.  Для всех    A О

VA , таких что встречаются в левой части правил
                    <A>  ® a

, построим команды вида:

                          f0( s 0 , e

        , <A> ) = ( s0 , aR

        ),

                     где aR

-зеркальное отображение a

.

               2. Для всех a ОVт

построим команды вида

                          f ( s0 , a , a ) = ( s0 , $ )

               3. Для перехода в конечное состояние построим команду

                  f ( s0 , e , h0 ) = ( s0 , $ )

               4. Начальную конфигурацию автомата определим в виде: