1. Контекстно-свободные грамматики и магазинные автоматы. (та)

Грамматика типа 2 (контекстно-свободная), продукции которой имеют вид :

А  , AW ,   (VW)*

Контекстно-свободная — магазинный автомат, представляющий собой некоторое устройство управление, имеется полу - лента справа и слева и стек. Используется: 1) для распознавания строк принадлежащих некоторой грамматике. 2) Порождение строк принадлежащих некоторому языку (генерация кода). 3) Объединения задача распознавания и порождения для организации процесса компиляции. М=<V,Q,A,P,B,I>, где V- входной алфавит, Q - множество состояний, A - внутренний алфавит стека, P - отображения QV (QVA  QAB), B - выходной алфавит, I- начальная конфигурация

Магазинный автомат –(М ) – совокупность пяти (шести ) объектов М=<A,Q,S,P,I,(B)> A- конечный входной алфавит Q- множество состояний P- система комманд магазинного автомата S - конечный стековый алфавит B- выходной алфавит Р : Q*S*A-> Q*S* P={qi sj a n -> qi’ s’ } I=qi a – начальное состояние и строка состояния стека в начальный момент времени .

Теорема (о КС- грамматиках и магазинных автоматах )

Для любого языка порождаемого КС – грамматикой существует магазинный автомат (возможно недетерминированный ) такой , что его множество принимаемых строк совпдает с этим языком . Верно и обратное . Если L(M) язык принимаемый некоторым магазинным автоматом то этот язык может быть порожден КС- грамматикой