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

1. Краткое содержание

1.1 От конечных автоматов к автоматам с магазином

Мы уже знаем, что конечные автоматы (FSA) распознают регулярные языки. Но у FSA есть фундаментальное ограничение: у них есть лишь фиксированная конечная память — по сути только текущее состояние. Из-за этого некоторые языки распознать нельзя, например : машине пришлось бы помнить произвольно большое число символов a.

Чтобы выйти за пределы регулярных языков, нужна модель с большей памятью. Естественное расширение — «прицепить» к FSA магазин (стек), получив автомат с магазином (PDA). Название «pushdown» отражает именно природу стека: новые элементы кладутся сверху, а снимается всегда верхний.

От FSA к PDA: тот же конечный контроллер получает неограниченный стек

Неформально:

• FSA = блок конечного управления (только состояния)
• PDA = блок конечного управления + бесконечный стек

Иерархия моделей вычислений (от более слабой к более сильной) выглядит так:

• Комбинационная логика — без памяти
• Конечные автоматы (FSA) — фиксированная ограниченная память (фактически только текущее состояние)
• Автоматы с магазином (PDA) — неограниченная память в виде стека (может расти без предела)
• Машины Тьюринга — полноценная лента для чтения/записи (максимальная мощность)

PDA находятся ровно на ступень выше FSA и распознают контекстно-свободные языки (КС-языки, CFL), к которым относится большинство синтаксических конструкций языков программирования. Поэтому PDA — в центре компиляции: синтаксис языков программирования контекстно-свободен.

1.2 Стек: краткое напоминание

Стек — структура данных «последним пришёл — первым ушёл» (LIFO). Представьте стопку подносов в столовой: добавлять и снимать можно только сверху.

Дисциплина стека LIFO, которую используют PDA

Операции:

• Push: положить новый символ на вершину стека.
• Pop: снять верхний символ со стека (и одновременно «прочитать» его).

У PDA стек изначально содержит особый символ дна стека , который играет роль сторожевого маркера низа. Когда сверху , стек можно считать «пустым».

Пример — push , , , затем pop:

1. Начальный стек: только внизу
2. Push : стек = (сверху вниз)
3. Push : стек =
4. Push : стек =
5. Pop: снимаем ; стек =

Последним положенный символ всегда снимается первым. Это свойство LIFO делает стек удобным для сопоставления вложенных структур вроде сбалансированных скобок.

Историческая справка: идею стека ввёл Алан Тьюринг в работе 1946 года об Automatic Computing Engine (ACE); операции он называл BURY и UNBURY и использовал их в теории подпрограмм.

1.3 Неформальное описание PDA

У PDA три компонента:

1. Входная лента — только для чтения, слева направо (входная строка)
2. Блок конечного управления — как у FSA, хранит текущее состояние
3. Стек неограниченного размера — дополнительная память; контроллер читает вершину и заменяет её

Шаг PDA: прочитать вход, посмотреть вершину стека, перейти к новой конфигурации

На каждом шаге PDA одновременно смотрит на три вещи:

• Текущее состояние
• Следующий входной символ (или для «тихого» шага)
• Вершину стека

Исходя из этой тройки, он:

1. Переходит в новое состояние
2. Сдвигает головку по входу (или остаётся на месте при -переходе)
3. Заменяет верхний символ стека на строку

С помощью стека PDA может:

• Кладуть (push) символы на стек (заменить верх на , тогда сверху)
• Снимать (pop) верхний символ (заменить верх на )
• Не менять стек (заменить верх на )
• Делать -переходы — переходы без чтения входа, только со изменением стека

Критерий принятия: строка принимается, если после полного чтения PDA находится в принимающем (финальном) состоянии. Содержимое стека в конце для принятия финальным состоянием не важно.

1.4 Формальное определение PDA

Автомат с магазином (PDA) — это 7-кортеж:

где:

• — конечное множество состояний
• — конечный входной алфавит (символы, читаемые с ленты)
• — конечный алфавит магазина (символы, которые могут лежать на стеке; и могут пересекаться)
• — функция переходов (частичное отображение в множество возможных исходов)
• — начальное состояние
• — начальный символ стека (маркер дна, кладётся на стек в начале)
• — множество принимающих (финальных) состояний

Как читать функцию переходов: переход означает:

В состоянии , читая входной символ (или ), при вершине стека : перейти в и заменить строкой .

На стрелках в диаграммах пишут: — «прочитать с входа, снять со стека, положить ».

• Чтобы положить под : (заменить на ; теперь сверху )
• Чтобы снять :
• Чтобы оставить стек неизменным:

Ограничения на :

• На стеке всегда есть хотя бы
• никогда не удаляется со стека
• Не кладутся дополнительные копии на стек

1.5 Детерминированные автоматы с магазином (DPDA)

Общий PDA выше недетерминированен: может содержать несколько пар, то есть «выбор» между переходами. Недетерминированные PDA (NPDA) — мощный инструмент, но на практике компиляторы используют детерминированные PDA.

PDA — детерминированный автомат с магазином (DPDA), если выполняются оба условия:

1. Не больше одного перехода на шаг: для всех , и множество содержит не более одного элемента.
2. Нет конфликта между чтением входа и -переходами: для всех , и множества и не могут быть оба непустыми.

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

Зачем нужно правило про : если бы одновременно и были непусты, автомат был бы недетерминирован — он мог бы либо съесть , либо сделать спонтанный шаг. DPDA такую двусмысленность запрещают.

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

1.6 Конфигурации и переходы

Чтобы формально описать работу PDA, вводят конфигурацию.

1.6.1 Конфигурация

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

где:

• — текущее состояние управляющего устройства
• — непрочитанный фрагмент входной строки
• — текущее содержимое стека (от верха к низу)

Соглашение: стек записывается сверху вниз. Если , то — вершина, — всё ниже.

Пример: конфигурация означает: автомат в состоянии , непрочитанный вход — , на стеке (сверху вниз) лежат , , .

Начальная конфигурация: для любой входной строки .

1.6.2 Переходы между конфигурациями

Символ («выводит за один шаг», «переходит к») описывает один шаг. Есть два случая:

Случай 1 — чтение входного символа: если определена, а в текущей конфигурации на вершине , а непрочитанный вход начинается с , то:

Словами: съесть со входа, снять со стека, положить , перейти в .

Случай 2 — -переход (спонтанный): если определена и на вершине :

Словами: не читать вход, снять , положить , перейти в .

Ключевая разница: в случае 1 головка входа сдвигается на один символ; в случае 2 остаётся на месте.

1.6.3 Многошаговое вычисление:

— рефлексивное транзитивное замыкание . То есть означает, что есть цепочка из нуля или более шагов:

Отношение описывает полный путь вычисления между конфигурациями.

1.6.4 Принятие строки PDA

Строка принимается PDA , если:

для некоторого и некоторого .

Проще говоря: из начальной конфигурации (состояние , весь вход , на стеке только ) можно дойти до конфигурации, где:

1. Весь вход прочитан (непрочитанное — )
2. Текущее состояние принимающее ()
3. Стек может быть любым ( произволен)

Язык, распознаваемый :

длянекоторых

1.7 Два режима принятия

PDA может принимать строку двумя способами:

• Принятие финальным состоянием: вход полностью прочитан и автомат в состоянии . Содержимое стека не важно.
• Принятие пустым стеком: вход полностью прочитан и на стеке только (фактически «пусто»). Состояние не важно.

Для недетерминированных PDA эти режимы эквивалентны: любой язык, принимаемый одним способом, можно принять и другим (построив другой PDA). Для детерминированных PDA режимы не эквивалентны.

Тонкость про пустой стек: языки, принимаемые пустым стеком, должны быть беспрефиксными (prefix-free): ни одна строка языка не является собственным префиксом другой. Как только стек «опустел» на , продолжить разбор продолжения уже нельзя.

1.8 Разобранный пример: PDA для

Классический пример: как PDA «считает» с помощью стека.

Стратегия: для каждого входного a положить на стек один символ . Когда начинаются b, снимать по одному на каждый b. Если ровно в момент, когда все b кончились, на стеке только , счётчики совпали.

Спецификация PDA:

• Состояния: (старт), (чтение a), (чтение b), (принятие)
• Алфавит стека:
• Переходы:

Переход	Запись	Смысл
		Первый a; положить над
		Каждый следующий a; ещё один
		Первый b; снять один
		Каждый следующий b; снять
		Вход исчерпан; сверху — значит все совпали; принять

Трассировка для входа "aabb":

Шаг	Состояние	Непрочитанный вход	Стек (сверху вниз)	Правило
1				: push
2				: push
3				: pop
4				: pop
5				: к принятию
6				ПРИНЯТО

Полное вычисление:

1.9 Ещё примеры PDA

1.9.1 PDA для

Стратегия: положить по одному на каждый a до единственного b. Символ b — «перекрёсток». После b снимать по одному на каждый a справа. Если в конце входа стек дошёл до , блоки a слева и справа одинаковой длины.

• Состояния: (старт, фаза push), (фаза pop после b), (принятие)
• Переходы:

Переход	Запись	Смысл
		Первый a до b: push
		Каждый следующий a до b$: push $A$ | | $q_0 \to q_1$ | $b,\, A / A$ | Видимb; стек не меняем, меняем состояние | | $q_1 \circlearrowleft$ | $a,\, A / \varepsilon$ | Каждыйaпослеb`: pop один
		Все совпали; принять

1.9.2 PDA для

Язык состоит из строк вида : строка , маркер центра , затем в обратном порядке. Символ — «осевая опора».

Стратегия: вся кладётся на стек. Прочитав , переключиться в режим pop: для каждого символа снимать согласованный символ со стека. Если после всего входа вернулись к — принять.

• Состояния: (фаза push), (фаза pop после ), (принятие)
• Ключевые переходы (фаза push, состояние , петли):
  • ; ; ; ; ;
• Опора (при чтении ): ; ; (все ведут )
• Фаза pop (, петли): ;
• Принятие: ()

1.9.3 PDA для сбалансированных круглых скобок

Язык сбалансированных (корректно вложенных) скобок — типичный контекстно-свободный язык. Интуитивно каждой ( нужна парная ), пары должны быть правильно вложены.

• Состояния: (старт), (работа), (принятие)
• Переходы:
  • : — первая (: push
  • : — каждая следующая (: push
  • : — каждая ): pop один (сопоставление с ()
  • : — вход кончился, «пустой» стек: принять

1.10 PDA и FSA: общая картина

• Каждый регулярный язык распознаётся PDA (достаточно симулировать FSA, не используя стек).
• PDA распознают языки, которые FSA не распознают (например, ).
• Значит, класс контекстно-свободных языков строго шире класса регулярных.

Классический PDA для aⁿbⁿ

• Регулярные языки языки, распознаваемые PDA (контекстно-свободные)
• Примеры КС, но не регулярных: , , сбалансированные скобки
• Примеры сильнее PDA: (нужно считать три величины одновременно — одного стека недостаточно)

Память:

• FSA: фиксированная ограниченная память (только состояние — фиксированное число бит)
• PDA: конечное управление, но не фиксированный объём памяти — стек может расти неограниченно
• Ключевая мысль: регулярные языки про ограниченную память; контекстно-свободные требуют неограниченной памяти (но со специфической структурой LIFO)

1.11 PDA и компиляторы

PDA напрямую связаны с тем, как устроены современные компиляторы. Компилятор переводит исходный код (например, C, Python) в другой язык (например, машинный). Он состоит из нескольких фаз:

Регулярные языки — собственное подмножество контекстно-свободных

1. Лексический анализ: разбивает исходный текст на лексемы (tokens) — минимальные осмысленные единицы (ключевые слова, идентификаторы, операторы и т.д.). Синтаксис лексем регулярный, поэтому эту фазу выполняет FSA (или движок регулярных выражений).
2. Синтаксический анализ (разбор): проверяет, что последовательность токенов соответствует грамматике языка. В языках программирования есть вложенные структуры (сбалансированные скобки, вызовы функций, арифметические выражения) — это контекстно-свободно. Эту фазу выполняет PDA.
3. Семантический анализ: типы, область видимости и т.п.
4. Генерация и оптимизация кода: построение и улучшение целевого кода.

Почему разбор — это PDA? В языках есть конструкции, требующие согласованных/вложенных структур:

• блоки {...} в C/Java
• begin...end в Pascal
• арифметические выражения в скобках
• вложенные вызовы функций

Именно то, с чем PDA справляются, а FSA — нет.

Лексический анализ на FSA, потому что токены (идентификаторы, числа, ключевые слова) описываются регулярными шаблонами. Например, идентификатор в Pascal соответствует регулярной схеме <letter>(<letter>|<digit>)*, что легко распознать FSA.

Синтаксический анализ на PDA, потому что правила вроде «выражение — это терм, затем оператор, затем другое выражение, возможно со скобками» — контекстно-свободны.

«Контекстно-свободные грамматики с 1960-х играют центральную роль в технологии компиляторов… Существует автоматная нотация, называемая ‘автомат с магазином’, которая описывает ровно все и только контекстно-свободные языки.» — Джон Е. Хопкрофт, Раджив Мотвани и Джеффри Д. Ульман

1.12 Лемма о накачке для КС-языков (лемма Бар-Хиллеля)

Как лемма о накачке для регулярных языков помогает доказывать нерегулярность, так и для КС-языков есть аналог.

1.12.1 Лемма о накачке для регулярных языков (напоминание)

Лемма о накачке (FSA): если — регулярный язык, то существует такое, что любое с можно записать как , где:

• (т.е. )
• для любого

Контрапозиция — рабочий инструмент: если для некоторого слова из нет такого разбиения, то не регулярен.

1.12.2 Лемма Бар-Хиллеля (лемма о накачке для КС-языков)

Лемма Бар-Хиллеля: если — контекстно-свободный язык (распознаётся PDA), то существует такое, что любое с можно записать как , где:

• (хотя бы один из , непуст)
• («средняя» часть не слишком длинная)
• для любого (одновременная накачка и одинаковым числом повторов сохраняет строку в )

Главное отличие от регулярной леммы: в регулярном случае качают один отрезок . В КС-случае качают два отрезка ( и ) синхронно — одинаковое число повторов .

Наглядная связь с деревьями разбора (нормальная форма Хомского): в достаточно высоком дереве разбора какой-то нетерминал повторяется. Два «рукава» от двух вхождений дают два накачиваемых отрезка и .

Интуиция Бар-Хиллеля: повтор нетерминала порождает два накачиваемых поддерева

1.12.3 Контрапозиция: как доказать «не КС»

Следствие (форма для доказательства): если для любого существует с такое, что для каждого разбиения с и найдётся , для которого , то не контекстно-свободен (ни один PDA его не распознаёт).

Игра в двух лицах:

Игрок 1 (противник)	Игрок 2 (вы)
Выбирает любое	Выбираете с
Выбирает разбиение с и	Находите , что

Вы выигрываете (и не КС), если всегда можете подобрать «побеждающее» .

1.12.4 Классический пример:

Утверждение: не распознаётся никаким PDA.

Набросок доказательства: пусть . Возьмём (тогда ). Для любого разбиения с и :

Расстояние от первого a до последнего c равно , но . Значит не может одновременно охватывать все три типа символов — там не более двух типов (только a, только b, только c, или a+b, или b+c).

Во всех случаях накачка при даёт строку с «сломанными» счётчиками:

• Если содержит только a: при накачке добавляются a, но не b и не c, получаем .
• Если только b: аналогично .
• Если только c: .
• Если пересекает a и b: добавляются a и b, но не c — строка не в .
• Если пересекает b и c: добавляются b и c, но не a — та же проблема.

Итак, во всех случаях . Следовательно не контекстно-свободен.

1.13 За пределами PDA: пределы КС-языков

Не все языки — КС. Канонический пример — . Чтобы его распознать, нужно сравнивать три счётчика одновременно, а стек поддерживает по сути один «линейный» счёт.

Для таких языков нужна более сильная модель — машина Тьюринга с полноценной лентой чтения/записи. Стек — деструктивная память: после pop символ исчезает. Лента персистентна: чтение не разрушает символ.

Иерархия языков повторяет иерархию машин:

• Регулярные — FSA
• Контекстно-свободные — PDA (память стека)
• Контекстно-зависимые и далее — машины Тьюринга (память ленты)

---

2. Определения

• Автомат с магазином (PDA): модель с конечным управлением, входной лентой и неогра­ниченным стеком. Формально — 7-кортеж . PDA распознают ровно класс КС-языков.
• Детерминированный PDA (DPDA): PDA, где (1) для всех (на шаг не больше одного перехода), и (2) из следует для всех (нет конфликта между чтением входа и -переходами).
• Недетерминированный PDA: может содержать несколько исходов. Авомат принимает, если существует последовательность выборов, ведущая к принятию.
• Стек: структура LIFO — основная память PDA. Операции: push (положить наверх) и pop (снять сверху).
• Алфавит магазина (): конечное множество символов на стеке. Обычно включает маркер дна .
• Символ дна стека (): специальный символ внизу стека изначально. Никогда не удаляется и не дублируется. Когда он сверху, стек «пуст».
• Входной алфавит (): конечное множество символов входной ленты. Смысл отделён от , хотя множества могут пересекаться.
• Функция переходов (): . Переход : из , читая (или ) и вершину , перейти в и заменить на .
• -переход: переход без чтения входа — меняются состояние и/или стек «спонтанно».
• Правило про (условие DPDA): если из есть -переход при вершине , то не должно быть перехода с чтением входа из того же при той же вершине .
• Конфигурация: тройка — снимок PDA: состояние , непрочитанный вход , стек (сверху вниз). Также «мгновенное описание PDA».
• Переход между конфигурациями (): один шаг. если ; либо если .
• Рефлексивно-транзитивное замыкание (): — ноль или более шагов от к .
• Принятие финальным состоянием: принимается, если для некоторых , . Финальный стек не важен.
• Принятие пустым стеком: принимается, если для некоторого (не обязательно из ). Для DPDA два режима не эквивалентны.
• Контекстно-свободный язык (КС, CFL): язык, распознаваемый PDA, или эквивалентно порождённый КС-грамматикой. Каждый регулярный — КС, обратное неверно.
• Лемма о накачке (регулярные языки): если регулярен, существует такое, что каждое с раскладывается , , , и .
• Лемма Бар-Хиллеля (КС): если КС, существует такое, что каждое с раскладывается , , , и .
• Компилятор: программа, переводящая исходный код одного языка (например, C) в другой (например, машинный), обычно через фазы: лексика, синтаксик, семантика, генерация кода.
• Лексический анализ: первая фаза; делит текст на токены. Использует FSA (регулярные шаблоны).
• Синтаксический анализ (парсинг): вторая фаза; проверяет соответствие грамматике и строит дерево разбора. Использует PDA для вложенных структур.
• Токен (лексема): минимальная осмысленная единица языка (например, идентификатор sum, оператор +, ключевое слово if). Выделяется на лексике.
• Дерево разбора (синтаксическое дерево): дерево грамматической структуры; листья — токены; внутренние узлы — правила.
• Абстрактное синтаксическое дерево (AST): упрощённое дерево для семантики, оптимизации и генерации.
• Беспрефиксный язык: в ни одна строка не является собственным префиксом другой. Языки, принимаемые DPDA пустым стеком, должны быть беспрефиксными.

---

3. Формулы

• Формальное определение PDA: где
• Запись перехода: — прочитать с входа (или ), снять , положить
• Push : заменить верх на — запись
• Pop верхнего :
• Стек не менять:
• Условие DPDA 1: для всех , ,
• Условие DPDA 2: для всех , ,
• Конфигурация: где , (остаток входа), (стек, сверху вниз)
• Переход (чтение входа): при
• Переход (): при
• Принятие финальным состоянием: для некоторых ,
• Распознаваемый язык:
• Лемма (регулярные): регулярен : , , разбиение , , ,
• Лемма Бар-Хиллеля (КС): КС : , , разбиение , , ,
• Контрапозиция (Бар-Хиллель): не КС, если , , такое что разбиений с и : с

---

4. Примеры

4.1. Построить DPDA для (Лаба 6, Задание 1)

Постройте DPDA, распознающий язык — символов a, затем ровно символов b.

Показать решение

Идея: на каждый прочитанный a нужно положить два символа стека (тогда для символов a накопится символов). Затем снимать по одному на каждый b. Когда все b прочитаны и на стеке только , соотношение выполнено.

DPDA для aⁿb²ⁿ

1. Спецификация PDA:

   • Состояния: (старт), (чтение a), (чтение b), (принятие)
   • Алфавит стека:

2. Переходы:

   Переход	Запись	Смысл
   		Первый a: положить два
   		Каждый следующий a: положить ещё два (чисто: заменить верхний на , добавляя два)
   		Первый b: pop один
   		Каждый следующий b: pop
   		Все сняты; принять

   Замечание про шаг push: при чтении a при вершине заменяем на — фактически сохраняем имеющийся и добавляем два сверху, то есть стек растёт на два на каждый a. Эквивалентно: каждый a должен добавить два символа — замена (плюс два) даёт соотношение .

3. Трассировка для "abb" (, ):

   • : стек =
   • : стек =
   • : стек =
   • : ПРИНЯТО

4. Трассировка для "aabbbb" (, ):

   • : стек =
   • : стек = (чисто +2: добавляет два)
   • : стек =
   • : стек =
   • : стек =
   • : стек = — (ОШИБКА: недостаток стека — неверно, перепроверить)

   Исправление: пересчитаем. Для : после первого a стек , затем заменяем верхний на для второго a: стек (это 3 символа + ). Нужно маркера для .

   Другой подход: аккуратнее: на каждый a класть ровно два , используя отдельное состояние для второго push.

   Переход	Запись	Смысл
   		Первый a: первый
   		Спонтанно: второй
   		Следующий a (первый из пары push)
   …	…	…

   Самый простой корректный вариант: на каждый a — два через вспомогательное состояние:

   • Состояния: (старт), (только что прочитан a, нужен второй ), (готовы читать a или b), (чтение b), (принятие)

   Переход	Запись	Смысл
   		Первый a: один
   		Второй (спонтанно)
   		Ещё a: первый из двух
   		Начало b: pop один
   		Каждый b: pop
   		«Пустой» стек: принять

Ответ: DPDA с вспомогательным состоянием для второго на каждый a, затем pop по одному на каждый b, распознаёт .

4.2. Построить DPDA для скобок арифметических выражений (Лаба 6, Домашнее задание 1)

Постройте DPDA, распознающий язык корректных скобок арифметических выражений (бинарные операции). Алфавит , где — термы, а + — бинарный оператор.

Примеры в языке: (a + a), ((a) + (a + a)), ((a + a)) Язык — синтаксически корректные выражения со скобочными подвыражениями.

Показать решение

Идея: задача про простую грамматику выражений. Главное ограничение — баланс скобок: каждой ( нужна ), вложенность корректна. Символы и + в этой упрощённой постановке — «наполнитель», не ломающий баланс.

Каркас DPDA для сбалансированных скобок в арифметических выражениях

Упрощение: для построения DPDA достаточно свойства баланса скобок. Символы и + должны появляться в допустимых позициях грамматики; моделируем это, отслеживая открытые скобки на стеке.

Грамматика (неформально):

• Выражение: терм, или ( выражение ), или выражение + выражение

В простом DPDA, отслеживающем только баланс скобок:

1. Состояния: (работа), (принятие)

   • Алфавит стека: , где маркирует открытую (

2. Переходы (петли на ):

   Запись	Смысл
   	Открыли ( при «пустом» стеке: push
   	( внутри другой: push
   	Закрыли ): снять парный
   	Прочитали терм : стек не меняем
   	Терм внутри скобок: стек не меняем
   	Оператор вне скобок: стек не меняем
   	Оператор внутри скобок: стек не меняем

3. Принятие: : — баланс.

4. Трассировка для "(a+a)":

   • : стек =
   • : стек =
   • : стек =
   • : стек =
   • : стек =
   • : ПРИНЯТО

Ответ: DPDA отслеживает баланс скобок стеком и принимает, когда скобки согласованы и вход полностью прочитан.

4.3. Построить DPDA для (Лаба 6, Задание 2)

Постройте DPDA для над алфавитом .

(Строка: непустая над , затем над , маркер , затем , затем .)

Показать решение

Идея: положить на стек все символы (для a — , для b — ), затем все символы (для d — , для e — ). При появлении перейти в режим pop: сначала согласовать (обращение ), затем .

1. Спецификация PDA:
   • Состояния: (push ), (push ), (pop ), (pop ), (принятие)
   • Алфавит стека:
2. Фаза 1 — push (состояние , петли):
   • ;
   • ;
   • ;
3. Переход к фазе push (): при первом d или e перейти в :
   • ; ; ;
4. Фаза 2 — push (, петли):
   • ;
   • ;
5. Опора на ( или , если пусто):
   • ; (верх — символ : фаза pop-)
   • ; ( не было: сразу pop-: )
6. Фаза 3 — pop (, петли):
   • ; (сопоставление , )
   • Переход к pop-, когда на вершине или : на : ;
7. Фаза 4 — pop (, петли):
   • ;
8. Принятие: :

Ответ: DPDA с фазами push , push , pop , pop (с опорой ) распознаёт .

4.4. Построить DPDA для сбалансированных круглых и квадратных скобок (Лаба 6, Задание 3)

Постройте DPDA для языка вложенных сбалансированных скобок над алфавитом .

Примеры в языке: (([])())(), (())[] Примеры не в языке: ([(]))()(), ([)]

Показать решение

Идея: стек хранит открытые разделители. Для ( кладём маркер , для [ — . При ) снимаем верх и проверяем, что это . При ] — что верх . Принимаем, когда вход кончился и на стеке только .

DPDA для сбалансированных круглых и квадратных скобок

Замечание: важно отвергнуть ([)] — закрывающие символы должны соответствовать последнему открытию. LIFO стека обеспечивает это естественно.

1. Спецификация:

   • Состояния: (старт, работа), (принятие)
   • Алфавит стека: , где для (, для [

2. Переходы (петли на , кроме финального перехода принятия):

   Запись	Смысл
   	( при пустом стеке: push
   	( при вершине : push
   	( при вершине : push
   	[ при пустом стеке: push
   	[ при вершине : push
   	[ при вершине : push
   	) при вершине : pop (совпало)
   	] при вершине : pop (совпало)

3. Принятие: : — всё согласовано, только .

4. Отклонение (неявно): если читается ), а сверху , перехода нет — автомат застревает и отвергает. Так корректно отвергается ([)].

5. Трассировка для "([])":

   • : стек =
   • : стек =
   • : стек =
   • : стек =
   • : ПРИНЯТО

Ответ: приведённый DPDA распознаёт язык вложенных сбалансированных скобок над .

4.5. Построить DPDA для (Лаба 6, Задание 4)

Постройте DPDA для , где — число вхождений символа в строку . Иначе говоря, — все строки над с равным числом a и b (в любом порядке).

Показать решение

Идея: в отличие от , здесь a и b могут чередоваться как угодно. Стек используем как счётчик: кладём за каждый a (когда стек только или только ), и за каждый b (когда только или только ). Если входной символ «гасит» вершину (a при вершине или b при вершине ), делаем pop. Это чистый баланс.

1. Спецификация:

   • Состояния: (работа), (принятие)
   • Алфавит стека:
   • на стеке — «лишние a»; — «лишние b»

2. Переходы (петли на ):

   Запись	Смысл
   	a при балансе: push (+1 к a)
   	a при избытке a: ещё
   	a при избытке b: снять один
   	b при балансе: push
   	b при избытке b: ещё
   	b при избытке a: снять один

3. Принятие: : — всё сократилось до : счётчики равны.

4. Трассировка для "abba":

   • : стек = (избыток a = 1)
   • : стек = (сокращение)
   • : стек = (избыток b = 1)
   • : стек =
   • : ПРИНЯТО

5. Трассировка для "aab" (должно отвергаться: ):

   • : стек =
   • : стек =
   • : стек =
   • Вход кончился; стек (не только ); -перехода принятия нет. ОТВЕРГНУТО

Ответ: приведённый DPDA использует стек как знаковый счётчик и распознаёт .

4.6. Построить DPDA для (Лаба 6, Задание 5)

Постройте DPDA для .

Показать решение

Идея: строка вида — внешний слой a, внутренний слой b, согласованный внутренний слой a, согласованный внешний слой b. Стек в двух фазах:

DPDA для aⁿbᵐaᵐbⁿ

• Фаза 1 (внешние a): положить копий для ведущих a.
• Фаза 2 (внутренние b): положить копий поверх .
• Фаза 3 (внутренние a): снять по одному на каждый a (согласование внутренних b и a).
• Фаза 4 (внешние b): снять по одному на каждый b (согласование внешних a и b).

1. Состояния: (внешние a), (внутренние b), (внутренние a), (внешние b), (принятие)

2. Переходы:

   Переход	Запись	Смысл
   		Первый внешний a: push
   		Ещё внешние a: push
   		Первый внутренний b: push над
   		Ещё внутренние b: push
   		Первый внутренний a: pop
   		Ещё внутренние a: pop
   		Первый внешний b: pop (все сняты)
   		Ещё внешние b: pop
   		Всё согласовано: принять

3. Трассировка для "abba" слишком коротка (минимум ):

   Трассировка для "abab" ():

   • : стек =
   • : стек =
   • : стек =
   • : стек =
   • : ПРИНЯТО

Ответ: DPDA с фазами внешних a, внутренних b, внутренних a, внешних b распознаёт .

4.7. Доказать, что не КС (Туториал 6, Пример 1)

Докажите леммой Бар-Хиллеля (леммой о накачке для КС-языков), что не является контекстно-свободным языком.

Показать решение

Идея: в числа a, b и c должны совпадать. Лемма Бар-Хиллеля накачивает два отрезка синхронно, но любое «окно» длины внутри охватывает не больше двух типов символов. Накачка ломает хотя бы один счётчик.

1. От противного: пусть КС. Пусть — длина накачки из леммы Бар-Хиллеля.
2. Слово: , .
3. Любое разбиение с и .
4. Где может лежать : расстояние от первого a до последнего c равно . Так как , окно не может одновременно покрыть все три типа. Возможны:
   • только a, или только b, или только c, или
   • a+b (без c), или b+c (без a)
5. Накачка при : рассмотрим . Во всех случаях:
   • Если только из a: добавляются a, не b и не c — больше a, чем b и c. .
   • Если только из b: аналогично .
   • Если только из c: .
   • Если пересекает a и b: добавляются a и b, не c. .
   • Если пересекает b и c: добавляются b и c, не a. .
6. Вывод: во всех случаях — противоречие с леммой. Значит не КС.

Ответ: не контекстно-свободен.

4.8. Построить DPDA для (Туториал 6, Пример 2)

Постройте DPDA для и выполните трассировку на входе "aabb".

Показать решение

Идея: считать a стеком: по одному на каждый a, затем по одному pop на каждый b. Если после всех b на стеке только , длины совпали.

DPDA для трассировки aⁿbⁿ

1. Спецификация PDA:

   • Состояния: (старт), (чтение a), (чтение b), (принятие)
   • Алфавит стека:
   • Входной алфавит:

2. Переходы:

   Переход	Запись	Смысл
   		Первый a; push над
   		Дополнительные a; каждый раз push
   		Первый b; pop один
   		Дополнительные b; каждый раз pop
   		Вход кончился; сверху — все совпали; принять

3. Проверка детерминизма:

   • У каждого не больше одного исхода — условие 1.
   • -переход использует вершину . Из нет читающего вход перехода при вершине — условие 2.

4. Трассировка для "aabb":

   Шаг	Состояние	Непрочитанный вход	Стек	Правило
   1				: push
   2				: push
   3				: pop
   4				: pop
   5				: к принятию
   6				ПРИНЯТО

   Полная цепочка конфигураций:

Ответ: DPDA с состояниями (принимающее) и указанными переходами распознаёт .

4.9. Построить DPDA для (Туториал 6, Пример 3)

Постройте DPDA для .

Показать решение

Идея: по одному на каждый a до единственного b. Символ b — опора: переключение из режима push в pop. После b — по одному pop на каждый a справа. Равенство чисел a слева и справа.

1. Спецификация:

   • Состояния: (старт, фаза push), (фаза pop после b), (принятие)
   • Алфавит стека:

2. Переходы:

   Переход	Запись	Смысл
   		Первый a до b: push
   		Каждый следующий a до b: push
   		Прочитали b: стек не меняем, переход в pop
   		Каждый a после b: pop
   		Все совпали; принять

3. Трассировка для "aba":

   • : стек =
   • : стек = (без изменений)
   • : стек =
   • : ПРИНЯТО

4. Трассировка для "aabaa":

   • : стек =
   • : стек =
   • : стек =
   • : стек =
   • : стек =
   • : ПРИНЯТО

Ответ: DPDA с состояниями (принимающее) и указанными переходами распознаёт .

4.10. Построить DPDA для (Туториал 6, Пример 4)

Постройте DPDA для , где — обращение , а — особый разделитель. Входной алфавит .

Показать решение

Идея: положить на стек каждый символ (для a — , для b — ). Увидев центральный , перейти в режим pop и согласовывать со стеком. Так как — обращение , сверху вниз стек должен совпасть с .

1. Спецификация:

   • Состояния: (фаза push), (фаза pop), (принятие)
   • Алфавит стека: , где кодирует a, — b

2. Переходы:

   Фаза push (, петли):

   Запись	Смысл
   	Первый a: push
   	Первый b: push
   	Следующий a при вершине : push
   	Следующий a при вершине : push
   	Следующий b при вершине : push
   	Следующий b при вершине : push

   Опора (чтение , , стек не меняется):

   Запись	Смысл
   	пусто: перейти в pop
   	при вершине : в pop
   	при вершине : в pop

   Фаза pop (, петли):

   Запись	Смысл
   	a и вершина : совпало, pop
   	b и вершина : совпало, pop

   Принятие: : — всё совпало.

3. Трассировка для "abcba" (, ):

   • : стек =
   • : стек =
   • : стек = (без изменений)
   • : стек =
   • : стек =
   • : ПРИНЯТО

Ответ: DPDA с состояниями (принимающее) и указанными переходами распознаёт .