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

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



 

Утверждение. Если Г = { 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. Начальную конфигурацию автомата определим в виде:


                    ( s0 , w , h0<I> ),


          где w  - заданная цепочка, записанная на входной ленте.

          Автомат, построенный по приведенным выше правилам, работает следующим образом. Если в вершине магазина находится терминал, и символ, читаемый с входной ленты, совпадает с ним, то по команде типа (2) терминал удаляется из магазина, а входная головка сдвигается. Если же в вершине магазина находится нетерминал, то выполняется команда типа (1), которая вместо терминала записывает в магазин цепочку, представляющую собой правую часть правила грамматики. Следовательно, автомат, последовательно заменяя нетерминалы, появляющиеся в вершине магазина, строит в магазине левый вывод входной цепочки, удаляя полученные терминальные символы, совпадающие с символами входной цепочки. Это означает, что каждая цепочка, которая может быть получена с помощью левого вывода в грамматике Г, допускается построенным автоматом М.

          Пред.Страница 

          След.Страница   Раздел   Содержание


          Содержание раздела