Распознающий автомат для КС-языков

Для автоматных языков роль распознавателя может выполнять детерминированный конечный автомат.

Существует ли универсальный автоматный распознаватель КС-языков? Да, существует.

Для произвольной КС-грамматики может быть построен недетерминированный автомат с магазинной памятью, принимающий язык, порождаемый этой грамматикой.

Автомат с магазинной памятью (магазинный автомат, МП-автомат) подобен конечному автомату, оснащенному дополнительным запоминающим устройством со стековой дисциплиной «последним пришел — первым ушел».

Переходы МП- автомата определяются не только входным символом и текущим состоянием, но и значением вершины стека — элемента, поступившего в магазин последним.

В литературе на русском языке стек часто называют «магазином» по аналогии с магазином автоматического оружия: патрон, заряженный в магазин последним, выстреливается первым.

Недетерминированный МП-автомат — это не что иное, как устройство, реализующее перебор с возвратами. В этом смысле он эквивалентен обсуждавшемуся выше общему алгоритму распознавания КС-языков и так же неэффективен.

Для КС-грамматик, подчиняющихся определенным ограничениям, могут быть построены эффективные детерминированные магазинные автоматы, которые могут использоваться на практике для трансляции языков программирования.