8 МП автоматы

Автомат с магазинной памятью (МП-автомат) — это автомат, в котором помимо ограниченной памяти, хранящей текущее состояние, имеется потенциально бесконечная память, используемая как стек (магазин). В таком автомате в каждый момент доступен только тот элемент, который был добавлен позже остальных присутствующих на данный момент элементов. Формальное определение МП-автомата содержит семь компонент: Σ — входной алфавит; Γ — алфавит стека, то есть символы, которые можно добавлять в стек; Q — множество состояний автомата; q0 ∈ Q — начальное состояние автомата; Z0 ∈ Γ — единственный символ, находящийся в стеке при начале работы автомата; δ : Q × {Σ ∪ ε} × Γ → 2Q×Γ∗ — функция переходов; F — множество принимающих состояний. МП-автоматы распознают в точности контекстно-свободные языки. 00:06 Введение в контекстно-свободные грамматики и МП-автоматы 00:39 Построение МП-автомата 02:00 Правила грамматики и МП-автомата 04:18 Доказательство леммы 12:11 Обратная индукция 16:26 Заключение 17:58 Третий случай 19:24 Переход 21:05 Стек и моменты времени 24:29 Вывод слова 30:32 Доказательство 35:33 Обратная сторона 38:08 Введение в правила грамматики 39:39 Переходы и отслеживание символов 41:21 Перестроение КС грамматики 45:14 Доказательство леммы 50:34 Индукция по длине вывода 57:42 Заключение 58:48 База индукции 01:01:03 Переход 01:03:11 Доказательство леммы 01:06:07 Завершение доказательства 01:08:01 Вопросы и планы на следующую лекцию