8 МП автоматы

Автомат с магазинной памятью (МП-автомат) — это автомат, в котором помимо ограниченной памяти, хранящей текущее состояние, имеется потенциально бесконечная память, используемая как стек (магазин). В таком автомате в каждый момент доступен только тот элемент, который был добавлен позже остальных присутствующих на данный момент элементов. Формальное определение МП-автомата содержит семь компонент: Σ — входной алфавит; Γ — алфавит стека, то есть символы, которые можно добавлять в стек; Q — множество состояний автомата; q0 ∈ Q — начальное состояние автомата; Z0 ∈ Γ — единственный символ, находящийся в стеке при начале работы автомата; δ : Q × {Σ ∪ ε} × Γ → 2Q×Γ∗ — функция переходов; F — множество принимающих состояний. МП-автоматы распознают в точности контекстно-свободные языки.

Видео 8 МП автоматы автора Сталинский Букварь