Разработка компиляторов




Магазинные автоматы


Магазинные автоматы, известные также как автоматы с магазинной памятью или как МП-автоматы, формально определяются следующим образом.

Определение. МП-автомат - это семерка, где:

  • Q - конечное множество состояний
  • - конечный входной алфавит
  • Г - конечный алфавит магазинных символов
  • -- функция перехода, отображение множества в множество конечных подмножеств множества
  • - начальное состояние управляющего устройства
  • - символ, находящийся в магазине в начальный момент (начальный символ)
  • - множество заключительных состояний.

Определение. Конфигурацией МП-автомата P называется тройка , где q - текущее состояние управляющего устройства, -- неиспользованная часть входной цепочки (если , то считается, что вся входная цепочка прочитана), - содержимое магазина (самый левый символ цепочки считается верхним символом магазина; если , то магазин считается пустым).

На каждом шаге работы МП-автомат может либо занести что-то в магазин, либо снять какие-то значения с его вершины. Отметим, что МП-автомат может продолжать работать в случае окончания входной цепочки, но не может продолжать работу в случае опустошения магазина.

Класс языков, распознаваемых МП-автоматами, в точности совпадает с классом языком, задаваемых КС-грамматиками (мы этого доказывать не будем).




Содержание  Назад  Вперед