Если — язык, принимаемый некоторым, возможно недетерминированным магазинным автоматом , то этот язык может быть порожден КС грамматикой, то есть существует грамматика , такая что .
ДОКАЗАТЕЛЬСТВО.
A. Заметим, что теорема 2.7 была теоремой синтеза, когда, имея грамматику, мы строим устройство, распознающее строки КС языка, порожденного этой грамматикой. Рассмотрим теорему 2.8. Эта теорема анализа, когда задано устройство и ставится задача найти формальное описание языка, принимаемого этим устройством.
B. Построим грамматику следующим образом:
1. Поставим в соответствии каждому знаку стекового алфавита нетерминальный знак грамматики таким образом, что из нетерминального знака могут быть выведены (порождены) строки в результате вывода которых автомат переходит из состояния в состояние и одновременно из стека извлекается знак.

Пример. Если стековый алфавит , а множество состояний , тогда алфавит нетерминальных знаков будет .

2. Множество продукций зададим следующим образом:
— Обозначим заключительное состояние как , если .
— Множество нетерминальных знаков определим как .
— Если имеется команда , где , , , то в множество продукций добавляем всевозможные продукции вида , где , где — число состояний автомата .
— Аксиомой грамматики объявим нетерминальный знак , где содержит множество строк, которые принимаются магазинным автоматом при переходе из начального состояния в конечное состояние, когда из стека извлекается знак .
Аксиому грамматики строим таким образом, что при извлечении из стека любого префикса начальной конфигурации, магазинный автомат переходит из начального состояния в заключительное состояние, что эквивалентно принятию такого множества строк, которое будет соответствовать построенной нами аксиоме.
C. Вывод. Видно, что при переходе из начального состояния в заключительное состояние магазинный автомат принимает такое множество строк, которые описываются построенными продукциями , которые, очевидно, определяют КС грамматику.
То есть произвольный магазинный автомат, если принимает какие–то строки, то их множество может бать порождено КС грамматикой.

ТЕМА 2.5. ДВУХСТЕКОВЫЙ АВТОМАТ

Определение. ДВУХСТЕКОВЫЙ АВТОМАТ это формальная система, задаваемая 6 объектами , где
— конечный входной алфавит,
— конечный выходной алфавит,
— множество состояний двухстекового автомата,
— стек просмотра назад,
— стек просмотра вперед,
система команд. Есть отображение множества декартового произведения множеств состояний двухстекового автомата, стека просмотра назад, входного алфавита и стека просмотра вперед в множество декартового произведения множеств состояний двухстекового автомата, стека просмотра вперед и стека просмотра назад.

Команды двухстекового автомата имеют вид

Если есть функция, то двухстековый автомат детерменированный.
-начальная конфигурация двухстекового автомата, где , а — есть начальное состояние стека.

Изобразим структуру двухстековаго автомата.

ТЕОРЕМА 2.9. О двухстековом автомате и контекстных грамматиках.
Для любого языка, порожденного контекстной грамматикой, существует двухстековый автомат, возможно недетерминированный, такой, что множество принимаемых им строк совпадает с множеством строк этого языка.
Верно и обратное: язык, принимаемый некоторым двухстековым автоматом может быть порожден контекстной грамматикой.

ТЕМА 2.6. КОНЕЧНЫЙ АВТОМАТ

Определение. КОНЕЧНЫЙ АВТОМАТ есть формальная система, задаваемая 5 объектами , где
— конечный входной алфавит,
— конечный выходной алфавит,
— конечное множество состояний конечного автомата,
— система команд конечного автомата. — есть отображение множества декартового произведения множеств состояний конечного автомата и входного алфавита в множество декартового произведения множеств состояний конечного автомата и выходного алфавита

— есть множество всевозможных команд вида
— начальная конфигурация конечного автомата, где .

Замечание. Иногда конечный автомат представляют как 5 объектов , где
— отображение (функция) переходов,
— отображение (функция) выходов.

Очевидно, что это определение, с точностью до начального состояния, эквивалентно предыдущему. Действительно, отображение декомпозируется на два отображения и . .
Заметим, что если — функция, то задание автомата во втором виде может привести к недетерминированности.
Изобразим структуру конечного автомата.

Пример. Пусть есть конечный автомат .

Представим данный конечный автомат в виде автоматной таблицы.

Представим данный конечный автомат в виде графа переходов конечного автомата.

В этом случае функции