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