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

B. Определим магазинный автомат следующим образом
— входной алфавит;
— множество состояний магазинного автомата;
— алфавит стека – объединение терминального, нетерминального алфавитов и знака – ограничителя стека;
Множество команд

Конфигурация , где — аксиома грамматики.
C. Определение автомата гарантирует, что для любого вывода в грамматике

Из входной очереди магазинного автомата удаляется строка , то есть автомат реализует левосторонний вывод.
D. ЛЕММА О левостороннем выводе в КС грамматике
Любая строка языка , порожденная КС грамматикой может быть получена в результате левостороннего вывода, когда в сентенциальной форме грамматики заменяется (раскрывается) самый левый нетерминальный знак.

ДОКАЗАТЕЛЬСТВО.
Достаточно показать что в грамматике из сентенциальной формы , где результат вывода не зависит от последовательности применения продукций .

Учитывая, что — произвольные подстроки сентенциальной формы, то тем самым мы показали, что результат вывода в грамматике не зависит от последовательности раскрытия нетерминальных знаков.
E. Магазинный автомат
1. Удаляет из входной очереди совпадающие с вершиной стека нетерминальные знаки (видно из системы команд).
2. Если на вершине стека находится нетерминальный знак, то он заменяется на строку, ему соответствующую, произвольным недетерминированным образом. , .
3. Когда стек исчерпан, то есть найден знак *, магазинный автомат переходит в заключительное состояние, выбрав предварительно из входной очереди последовательность терминальных знаков, которая может быть порождена грамматикой .
4. Если выбрана продукция в пункте 2, которая не использовалась для порождения строки во входной очереди, то автомат не остановится, то есть этот экземпляр автомата строку не распознает, но будет существовать экземпляр, который распознает эту строку.
Окончание доказательства.

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