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


Построение магазинного автомата - часть 2


                ( s0 , w , h0<I> ),

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


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

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

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




- Начало -  - Назад -  - Вперед -