Построение магазинного автомата
| Утверждение. Если Г = { 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), которая вместо терминала записывает в магазин цепочку, представляющую собой правую часть правила грамматики. Следовательно, автомат, последовательно заменяя нетерминалы, появляющиеся в вершине магазина, строит в магазине левый вывод входной цепочки, удаляя полученные терминальные символы, совпадающие с символами входной цепочки. Это означает, что каждая цепочка, которая может быть получена с помощью левого вывода в грамматике Г, допускается построенным автоматом М.
Пред.Страница
След.Страница Раздел Содержание