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

в качестве начального состояния автомата примем s0 и построим функцию переходов так:
               1.  Для всех    A О VA , таких что встречаются в левой части правил
                    <A>  ® a , построим команды вида:                      где aR -зеркальное отображение a .

               2. Для всех a ОVт построим команды вида

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

Hosted by uCoz