W7. Преобразователи с магазином (PDT), операции над языками DPDA, теория автоматов и модели вычислений

Автор

Manuel Mazzara

Дата публикации

5 марта 2026 г.

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

1.1 Напоминание: конечные преобразователи (FST)

Прежде чем вводить более мощный преобразователь с магазином (PDT), полезно вспомнить, как работает конечный преобразователь (FST), поскольку PDT — его прямое обобщение.

Конечный преобразователь (FST) — это конечный автомат (FSA), дополненный механизмом вывода. Формально FST — это кортеж , где:

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

Важное замечание: функция применяется только к строкам, которые принимаются базовым FSA. Если входная строка отвергается, её перевод не определён.

Как работает FST: при чтении каждого входного символа FST одновременно (a) меняет состояние (через ) и (b) записывает выходную строку (через ). На стрелке диаграммы переходов подпись имеет вид вход/выход, например a/A означает «прочитать с входа, записать на выход».

Пример — простой регистронный преобразователь:

Пусть (все строки над ) с переводом , .

У FST одно принимающее состояние с петлями:

  • : прочитать , вывести
  • : прочитать , вывести

На входе FST выдаёт .

Пример — FST с ограниченной областью:

Пусть внетсимволов с тем же переводом. Теперь FST имеет два состояния:

  • (принимающее): читает и выводит ; при чтении переходит в непринимающее «стоковое» состояние
  • (отвергающее): читает любой символ и выводит (строка всё равно будет отвергнута)

На входе выход — . На входе строка отвергается — перевод не определён.

Ограничение FST: как и у FSA, память только конечная и фиксированная (текущее состояние). Нельзя обрабатывать языки, где нужен «счёт», например , если выход должен отслеживать, сколько прочитано, чтобы выдать нужное число выходных символов. Нужен преобразователь с магазином (PDT).

1.2 Преобразователи с магазином (PDT)
1.2.1 Мотивация и наглядная картина

Преобразователь с магазином (PDT) расширяет автомат с магазином (PDA) выходной лентой так же, как FST расширяет FSA. PDT использует стек не только для распознавания языка (как в PDA), но и для помощи переводу: в стеке хранится промежуточная информация, нужная для корректного выхода.

Архитектура PDT состоит из четырёх частей:

  • Входная лента: только для чтения; символы читаются слева направо
  • Конечное управление: конечное множество состояний и логика переходов
  • Стек: память LIFO (последним пришёл — первым ушёл), может неограниченно расти
  • Выходная лента: только для записи; к ней дописываются выходные символы

PDT_arch input Входная лента ← только чтение → ctrl Конечное управление input->ctrl чтение stack Стек (LIFO) ctrl->stack push / pop output Выходная лента ← только запись → ctrl->output запись

Архитектура преобразователя с магазином: входная лента, конечное управление, стек и выходная лента

Стек — разрушающая память: символ, снятый со стека, исчезает. В этом и сила PDT, и его принципиальное ограничение.

Один переход PDT за атомарный шаг: читает входной символ (или ), смотрит вершину стека, меняет состояние, переписывает вершину стека и пишет на выходную ленту.

1.2.2 Нотация переходов

Переход из состояния в состояние изображается стрелкой с подписью:

где:

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

Альтернативная нотация отделяет двоеточием часть стека от выхода:

В литературе встречаются обе; смысл один.

То есть и на диаграмме объединяются в подпись .

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

Преобразователь с магазином — это 9-кортеж:

где:

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

Замечания:

  • — те же компоненты, что у обычного PDA-«распознавателя».
  • определена только там, где определена — на неопределённых переходах выхода нет.
  • Стек может быть нужен по двум разным причинам: (a) для распознавания языка, и/или (b) для перевода.
1.2.4 Конфигурации и переходы

Конфигурация PDT — это 4-кортеж:

где:

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

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

  • Шаг по входу (потребление символа ): если и , то:
  • -шаг (тихий, вход не читается): если и , то:

Важно: при -переходе непрочитанный вход не меняется (символ с входа не потребляется).

1.2.5 Условие принятия

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

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

Это согласуется с тем, как устроен перевод в FST: перевод определён только если строка принята.

1.3 Примеры PDT
1.3.1 Перевод

Пусть и (каждый символ «в верхний регистр»).

Идея: стек считает число (вталкивать на каждое ), затем проверяются с выводом на каждое совпадение с .

Состояния (принимающие):

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

PDT_anbn_AaBb start q0 q₀ start->q0 q1 q₁ q0->q1 a, Z₀/AZ₀, A q1->q1 a, A/AA, A q2 q₂ q1->q2 b, A/ε, B q2->q2 b, A/ε, B q3 q₃ q2->q3 ε, Z₀/Z₀, ε

PDT для перевода aⁿbⁿ → AⁿBⁿ

На входе : отвергается (не в ), перевод не определён.

1.3.2 Перевод

Пусть и (на выход только «-часть»).

Идея: на фазе вталкивания () ничего не выводить. На фазе снятия () выводить на каждое совпадение с .

  • : и — вталкивать без выхода
  • : — первое , снять , вывести
  • : — дальше , выводить
  • : — принять

Итог: .

1.3.3 Перевод

Пусть и (поменять блоки местами).

Идея: на фазе выводить (заранее «готовить» выход). На фазе выводить на каждое совпадение.

  • : и — вталкивать , на каждое выводить
  • : — снять , вывести
  • :
  • : — принять

Итог: . Стек даёт «перевёрнутые» переводы, недоступные FST.

1.3.4 Перевод (обращение строки)

Пусть и (обращение , — разделитель).

Идея (СНАЧАЛА ВТАЛКИВАНИЕ — ПОТОМ СНЯТИЕ): пока читается , каждый символ вталкивается в стек, без выхода. При разделителе прекращаем вталкивание и начинаем снимать — выводим каждым снятием. LIFO даёт символы в обратном порядке.

  • Состояние (ФАЗА ВТАЛКИВАНИЯ — БЕЗ ВЫХОДА):
    • ; ;
    • ; ;
  • Переход (КОНЕЦ ВТАЛКИВАНИЯ):
    • ;
  • Состояние (ФАЗА СНЯТИЯ — ФОРМИРОВАНИЕ ВЫХОДА):
    • ;
  • Переход (принимающее):

PDT_reverse start q0 q₀ (push) start->q0 q0->q0 a|b: push, без выхода q1 q₁ (снятие) q0->q1 c, A/ε,a | c, B/ε,b q1->q1 ε,A/ε,a | ε,B/ε,b q2 q₂ q1->q2 ε, Z₀/Z₀, ε

PDT для обращения wc → wᴿ

На входе : в стек , затем , затем — снять (выход ), снять (выход ). Итоговый выход: . ✓

Стек позволяет переводы, где выход не следует строго слева направо по входу.

1.4 Свойства замкнутости языков DPDA

Перейдём от преобразователей к базовому вопросу теории формальных языков: какие операции сохраняют класс языков, распознаваемых детерминированными автоматами с магазином (DPDA)?

Это вопрос свойств замкнутости. Класс языков замкнут относительно операции , если применение к языкам из всегда даёт язык из .

Формально: замкнут относительно , если для любых выполнено .

Зачем это нужно: для регулярных языков (FSA) класс замкнут по четырём стандартным операциям — объединение, пересечение, дополнение и разность. Интересно, есть ли у детерминированных контекстно-свободных языков (DPDA) такие же удобные свойства.

closure_overview FSA FSA: ∪✓ ∩✓ \✓ ᶜ✓ DPDA DPDA: ∪✗ ∩✗ \✗ ᶜ✓ FSA->DPDA

Свойства замкнутости: FSA и DPDA

Итог (сводная таблица):
FSA (регулярные) да да да да
DPDA (дет. КС-языки) нет нет нет да

Далее по очереди разберём каждую операцию и причину результата.

1.4.1 Замкнутость по объединению: НЕТ

Утверждение: класс языков DPDA не замкнут по объединению.

Контрпример: два языка над :

И , и по отдельности распознаются DPDA (каждый — детерминированный контекстно-свободный язык). Но их объединение

не распознаётся ни одним DPDA.

Наглядно: «проблема подготовки стека». Пока DPDA читает , он должен заранее — на фазе вталкивания — решить, готовить стек к символам (для ) или к (для ). Но это можно понять только после всех и начала . К этому моменту содержимое стека уже зафиксировано. NPDA мог бы «ветвиться», DPDA — нет.

Точнее: после в стеке закодировано . Читая , нельзя одновременно проверять и «против », и «против » — нужно зафиксировать интерпретацию.

В отличие от регулярных: для FSA объединение строится декартовым произведением; для DPDA общего аналога нет — стеки для и могут быть несовместимы.

DPDA не замкнут по .

1.4.2 Замкнутость по пересечению: НЕТ

Утверждение: DPDA не замкнут по пересечению.

Контрпример: языки над :

Оба распознаются DPDA:

  • : считать , по одному сопоставлять , затем принять любое положительное число .
  • : пропустить любое положительное число , считать , сопоставлять один к одному.

Пересечение:

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

DPDA не замкнут по .

Через дополнение: алгебраически, законы де Моргана:

Так как DPDA замкнут по дополнению (ниже), при замкнутости по пересечению получилась бы замкнутость по объединению — противоречие.

1.4.3 Замкнутость по дополнению: ДА

Утверждение: DPDA замкнут по дополнению.

Теорема: если , то .

Почему для NPDA дополнение «ломается», а для DPDA — нет: у NPDA строка может отвергаться на всех путях, но приниматься на другом; недетерминизм мешает просто «инвертировать» принятие. У детерминированного PDA на каждый вход одна вычислимая ветка — принятые и отвергнутые строки разделимы.

Набросок построения — почему недостаточно поменять местами финальные состояния:

Для FSA дополнение: поменять финальные и нефинальные. У PDA наивный приём ломается из-за -переходов: на входе машина в нефинальном , но -переходом доходит до финального . После «обмена» станет финальным — «дополненный» автомат тоже примет — неверно.

Правильное построение — три шага:

  1. Убрать циклы: привести DPDA к ациклическому виду — после прочтения всего входа дальнейших -ходов нет. Любой DPDA эквивалентен ациклическому DPDA (нетривиальный факт). Тогда проблема выше исчезает.
  2. Полнота : сделать переходы везде определёнными, добавив непринимающее «мусорное» состояние для всех «дыр». Тогда из каждой конфигурации ровно один следующий шаг.
  3. Обмен финальных и нефинальных: раз машина после полного чтения входа останавливается в однозначном состоянии без -неоднозначности, обмен и даёт язык-дополнение.

Зачем ацикличность: иначе после конца входа возможны бесконечные -циклы через и финальные, и нефинальные состояния. С ацикличностью после исчерпания входа — одно ясное состояние.

DPDA замкнут по .

1.4.4 Замкнутость по разности: НЕТ

Утверждение: DPDA не замкнут по разности множеств.

От противного: пусть замкнут по . Для любых :

По дополнению . Тогда , значит — противоречие с незамкнутостью по .

DPDA не замкнут по .

Сравнение с регулярными: у FSA все четыре операции; у дет. КСЯ профиль асимметричен — только дополнение.

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

Лемма Бар-Хиллеля обобщает лемму о накачке с регулярных языков на контекстно-свободные. Как лемма о накачке для регулярных даёт необходимое условие регулярности, Бар-Хиллель даёт необходимое (но не достаточное) условие контекстно-свободности.

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

причём:

  1. (накачиваемые части не обе пусты)
  2. (окно накачки ограничено)
  3. для всех

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

Применение — не КС-язык:

не распознаётся ни одним PDA. Доказательство через Бар-Хиллель:

Пусть КС; — константа леммы. Возьмём . Для любого разбиения с и :

  • короткое, значит пересекает не больше двух из трёх блоков (, , ).
  • Накачка вверх () увеличивает не более двух типов символов, не все три поровну.
  • Тогда имеет неравные числа , , — не в .

Противоречие. Значит не контекстно-свободен.

1.6 Стек как разрушающая память и пределы PDA
1.6.1 Разрушающая и постоянная память

У PDA стек разрушающий: снятый символ не восстановить. Поэтому:

  • PDA распознаёт : операций push на , затем по одному pop на каждый .
  • PDA не распознаёт : для снова нужно знать , а стек уже «использован» на .

Нужна постоянная (читаемая/записываемая) память — устройство, где ячейку можно прочитать без уничтожения. Это мотивация машин Тьюринга с неограниченной лентой чтения-записи вместо стека.

1.6.2 Иерархия языков

lang_hierarchy reg Регулярные языки (FSA) cfl Контекстно-свободные (PDA) reg->cfl  напр. aⁿbⁿ — КС,  не регулярный re Перечислимые (машины Тьюринга) cfl->re  напр. aⁿbⁿcⁿ — переч.,  не КС

Иерархия языков: регулярные ⊂ КС ⊂ перечислимые

Иерархия по моделям:

  • Регулярные ⊂ контекстно-свободные (КСЯ) ⊂ перечислимые (всё, что считает МТ)

Границы:

  • : не регулярный (лемма о накачке), но КС (PDA)
  • : не КС (Бар-Хиллель), но вычислим МТ
  • : КС (NPDA), но не детерминированный КС-язык
1.7 Почему PDA в центре компиляторов

PDA — не только абстракция: они напрямую связаны с построением компиляторов.

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

Стек в PDA — политика LIFO. Она как раз подходит для вложенных синтаксических конструкций:

  • Арифметика со скобками: (a + (b * c))
  • Блочная структура begin/end или {/}
  • Цепочки вызовов (каждый вызов — кадр на стек, возврат — снятие)

Типичные фазы компилятора:

  • Лексический анализ: токены — часто FSA
  • Синтаксический анализ (разбор): грамматика программы — NPDA (КС-грамматики описывают большую часть синтаксиса языков программирования)
  • Семантика, генерация кода, оптимизация — дальше

Поэтому синтаксис почти всех ЯП задаёт контекстно-свободной грамматикой, а парсеры — по сути PDA.

1.7.2 Фиксированная и неограниченная память
  • FSA: память ограничена числом состояний — не сосчитать произвольное .
  • PDA: состояний конечно, но стек неограничен — можно сосчитать любое вталкиваниями.

Для нужен счёт до произвольного . FSA с состояниями ошибётся при . PDA со стеком справляется для всех .

1.8 Теория автоматов и модели вычислений
1.8.1 Что такое теория автоматов?

Теория автоматов — раздел теоретической информатики, изучающий:

  • Абстрактные математические машины (автоматы) и их вычислительные свойства
  • Задачи, которые решают разные типы автоматов

Слово automaton (мн.ч. automata) от греч. αὐτόματον — «самодвижущийся». У Гомера — про автоматические двери и статуи.

1.8.2 Зачем изучать теорию автоматов?
  • Автомат — конечное описание языка, который может быть бесконечным
  • Автоматы — теоретические модели вычислителей для строгих доказательств о разрешимости и сложности
  • Практика: компиляторы, проверка моделей, протоколы, поиск по шаблону
1.8.3 Модели вычислений

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

Последовательные модели:

  • FSA — ограниченная выразительность, фиксированная память; шаблоны, проверка моделей
  • PDA — стек, вложенность; основа разбора
  • Машина Тьюринга — неограниченная лента чтения-записи; общая последовательная модель

Функциональные модели:

  • Лямбда-исчисление — редукция и применение функций

Параллельные модели:

  • Сети Петри — параллельные и распределённые системы

Список неполный (регистровые машины, клеточные автоматы и т.д.).

1.8.4 Применения FSA на практике

FSA широко используются:

  • Машины Мура/Мили — цифровые схемы
    • Мили по сути FST — выход на переходах
  • Лексический анализ: токены
  • Диаграммы состояний UML
  • Протоколы: турникеты, автоматы, сети

Главное ограничение FSA — фиксированная память: без счёта и без запоминания неограниченного объёма данных.

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

  • Конечный преобразователь (FST): FSA с выходом. 7-кортеж , где — выходной алфавит, — функция перевода. Перевод только для принятых строк.
  • Преобразователь с магазином (PDT): PDA с выходной лентой. 9-кортеж , где — выходной алфавит, — функция перевода. Стек хранит информацию и для распознавания, и для перевода.
  • Конфигурация PDT: 4-кортеж : состояние , непрочитанный вход , стек (верх первым), уже записанный выход .
  • Функция перевода (): задаёт выход на переходе. : в , читая при вершине , записать . Определена только там, где определена .
  • Метка перехода PDT: на стрелке (или ): прочитать , снять , втолкнуть , записать .
  • Замкнутость по операции: класс замкнут по , если для любых результат .
  • DPDA (детерминированный PDA): у каждой конфигурации не больше одного продолжения: для всех , и влечёт .
  • Детерминированный контекстно-свободный язык (DCFL): язык, распознаваемый некоторым DPDA. Класс DCFL строго вложен в класс CFL.
  • Ациклический PDA: для каждого входа вычисление всегда завершается; после исчерпания входа -переходов нет. Любой DPDA эквивалентен ациклическому DPDA.
  • Разрушающая память: свойство стека — снятый символ теряется безвозвратно. В отличие от ленты МТ, где чтение не стирает символ.
  • Лемма Бар-Хиллеля (накачка для КС-языков): если КС, то : любое , , раскладывается с , и .
  • Теория автоматов: раздел ТКС об абстрактных машинах и разрешимых ими задачах.
  • Модель вычислений: математическая схема: как из входа получают выход, как устроены память и шаги. Примеры: FSA, PDA, МТ, -исчисление, сети Петри.
  • Машина Тьюринга (МТ): модель с бесконечной лентой чтения-записи. Сильнее PDA: память не разрушается при чтении. Общая последовательная модель.
  • Контекстно-свободный язык (CFL): язык, распознаваемый (недетерминированным) PDA, эквивалентно порождённый КС-грамматикой. Все регулярные — КС, обратное неверно.

3. Формулы

  • Формально PDT: , где и
  • Переход PDT (по входу): при и
  • Переход PDT (): при и
  • Условие принятия и перевода PDT: для некоторого
  • Лемма Бар-Хиллеля: для КС , : , , разбиение с , и
  • Пересечение через разность: (доказательство незамкнутости DPDA по из незамкнутости по )
  • Де Морган (множества):
  • Сводка по DPDA: замкнутость только по ; нет замкнутости по , ,

4. Примеры

4.1. Построить DPDT, переводящий в (Лаба 7, Задание 1)

Постройте детерминированный преобразователь с магазином, который принимает , где , и переводит в (оставить ровно символов a и символов b, лишние b отбросить).

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

Идея: на каждое a втолкнуть (и вывести a). На фазе b снимать по и выводить b — когда стек «опустел» (все сопоставлены), дочитывать оставшиеся b без выхода.

dpdt_trim_b start q0 q0 start->q0 q0->q0 a, Z₀/AZ₀, a a, A/AA, a q1 q1 q0->q1 b, A/ε, b q1->q1 b, A/ε, b q2 q2 q1->q2 ε, Z₀/Z₀, ε q2->q2 b, Z₀/Z₀, ε

DPDT: перевод aⁿbᵐ при n ≤ m в aⁿbⁿ

  1. Состояния: (чтение a), (чтение b, стек ещё не пуст до ), (лишние b после опустошения счётчика — принимающее)

  2. Переходы:

    От К Метка Смысл
    Втолкнуть , вывести a
    Втолкнуть , вывести a
    Первое b: снять , вывести b
    Ещё b: снять , вывести b
    Стек без : все a сопоставлены, фаза «лишние b»
    Лишние b: игнорировать (без выхода)

  3. Принятие: принимающее (после -перехода, на стеке только ). Условие обеспечивается: без фазы вталкивания в в не попасть.

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

    • a: втолкнуть , выход a
    • a: втолкнуть , выход a
    • b: снять , выход b
    • b: снять , выход b
    • -переход в (на стеке )
    • b: снять без выхода
    • Конец: принимает. Выход: . ✓

Ответ: при . Вывести все a и первые символов b; остальные b отбросить.

4.2. Построить DPDT, обращающий строки в (Лаба 7, Задание 2)

Постройте детерминированный преобразователь с магазином, распознающий и переводящий в (обращение ).

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

Идея: LIFO стека даёт обращение. Втолкивать каждый символ без выхода. Увидев , перейти к снятию — выводить каждый снятый символ (обратный порядок).

dpdt_reverse start q0 q0 push start->q0 q0->q0 a, */A*, ε b, */B*, ε q1 q1 снятие q0->q1 c, A/ε, a c, B/ε, b q1->q1 ε, A/ε, a ε, B/ε, b q2 q2 q1->q2 ε, Z₀/Z₀, ε

DPDT: читает xc, выдаёт xᴿ

  1. Состояния: (фаза вталкивания — ), (фаза снятия после ), (принимающее)

  2. Переходы:

    От К Метка Смысл
    Втолкнуть , без выхода
    Втолкнуть , без выхода
    Втолкнуть под , без выхода
    Втолкнуть , без выхода
    Втолкнуть , без выхода
    Втолкнуть под , без выхода
    : снять , вывести a
    : снять , вывести b
    Снять , вывести a
    Снять , вывести b
    Стек пуст до маркера: принять

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

    • Втолкнуть , (без выхода)
    • Прочитать c: снять , выход b
    • : снять , выход a
    • : вершина → принять. Выход: . ✓

Ответ: . Фаза вталкивания для ; фаза снятия даёт .

4.3. Построить DPDT, переводящий в (Лаба 7, Задание 3)

Постройте DPDT, принимающий и и переводящий в (отбросить хвост ).

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

Идея: на ведущие a выводить a и вести счётчик в стеке. На каждое b выводить b. После b на хвостовые a снимать стек без выхода — при совпадении чисел принять.

dpdt_drop_suffix start q0 q0 start->q0 q0->q0 a, Z₀/AZ₀, a a, A/AA, a q1 q1 q0->q1 b, A/A, b q1->q1 b, A/A, b q2 q2 q1->q2 a, A/ε, ε q2->q2 a, A/ε, ε q3 q3 q2->q3 ε, Z₀/Z₀, ε

DPDT: aⁿbᵐaⁿ → aⁿbᵐ

  1. Состояния: (ведущие ), (), (хвостовые ), (принимающее)

  2. Переходы:

    От К Метка Смысл
    Ведущее a: втолкнуть , вывести a
    Ещё ведущие a: втолкнуть , вывести a
    Первое b: стек не менять, вывести b
    Ещё b: вывести b, стек не трогать
    Первое хвостовое a: снять , без выхода
    Ещё хвостовые a: снять , без выхода
    Стек без : хвост согласован — принять

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

    • a, a: втолкнуть , выход a; то же для второго
    • три b: выход b, b, b (стек )
    • два a: снять , без выхода; снова
    • → , принять. Выход: . ✓

Ответ: . Вывести ведущие a и все b; хвостовые a только проверить.

4.4. Построить DPDT, переводящий в (Лаба 7, Задание 4)

Постройте DPDT, принимающий и переводящий в (оставить только первые символов b, «лишние» символов b, «оплаченные» символами c, отбросить на выходе).

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

Идея: из следует символов b. Вывести a, сопоставить ровно символов b с втолкнутыми (на каждое совпадение выводить b), затем без выхода прочитать ещё символов b, затем проверить символов c с выводом c.

dpdt_ibjc start q0 q0 start->q0 q0->q0 a, Z₀/AZ₀, a a, A/AA, a q1 q1 q0->q1 b, A/ε, b q1->q1 b, A/ε, b q2 q2 q1->q2 b, Z₀/BZ₀, ε q2->q2 b, B/BB, ε q3 q3 q2->q3 c, B/ε, c q3->q3 c, B/ε, c q4 q4 q3->q4 ε, Z₀/Z₀, ε

DPDT: aⁱbʲcᵏ при i + k = j, перевод в aⁱbⁱcᵏ

  1. Стратегия:

    • На каждое a втолкнуть (вывести a).
    • Сопоставлять b с (снять , вывести b) — после символов b на стеке только .
    • Дальше читать b, вталкивая (без выхода) — «лишние» b.
    • Сопоставлять c с (снять , вывести c).
    • Принять, когда и , и исчерпаны по смыслу построения.

  2. Состояния: (a), (b против ), (лишние b, вталкивание ), (c против ), (принимающее)

  3. Переходы:

    От К Метка Смысл
    Втолкнуть , вывести a
    Втолкнуть , вывести a
    Первое b: снять , вывести b
    Ещё b против : снять, вывести b
    Стек без (прочитано символов b): фаза лишних b
    Ещё лишние b: втолкнуть , без выхода
    Первое c: снять , вывести c
    Ещё c: снять , вывести c
    Всё согласовано: принять

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

    • Втолкнуть , выход a, a
    • Снять , выход b; снять , выход b
    • Втолкнуть , (два лишних b)
    • Снять , выход c; снять , выход c
    • Вершина → принять. Выход: . ✓

Ответ: . Две фазы стека: сначала снятие против b (с выводом b), затем вталкивание для лишних b, затем снятие против c (с выводом c).

4.5. Построить DPDT, переводящий в (Лаба 7, Задание 5)

Постройте DPDT, принимающий и переводящий в .

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

Идея: — число b между и . Стратегия: на каждое a втолкивать два символа на стек (и один раз вывести a). На каждое b снимать один маркер; выводить b только для «первичных» снятий в пределах .

dpdt_range start q0 q0 start->q0 q0->q0 a, */SP*, a q1 q1 q0->q1 b, P/ε, b q1->q1 b, P/ε, b q2 q2 q1->q2 b, S/ε, ε q3 q3 q1->q3 ε, Z₀/Z₀, ε q2->q2 b, S/ε, ε q2->q3 ε, Z₀/Z₀, ε

DPDT: aⁿbᵐ при n ≤ m ≤ 2n, перевод в aⁿbⁿ

Проще: на каждое a — два маркера на стеке, снятие по одному на каждое b. Выход при корректном диапазоне .

  • Фаза вталкивания: на каждое a — и . Вывести a.
  • Фаза снятия: на каждое b снять один маркер. Выводить b только для первых снятий.
  • Принятие: когда маркеры исчерпаны при .

Упрощённая схема переходов:

Состояния: (a), (b, снятие первой «половины» маркеров — с выходом b), (лишние b, вторая «половина» — без выхода), (принимающее)

Символы стека: (первичный — даёт выход b) и (вторичный — без выхода). На каждое a втолкнуть , затем .

От К Метка Смысл
Втолкнуть и ; вывести a
Втолкнуть затем над существующим ; вывести a
Втолкнуть затем над ; вывести a
Первое b по первичному маркеру: снять , вывести b
Ещё b против : снять, вывести b
b против вторичного: снять , без выхода
Ещё b против : снять, без выхода
Сняты только (ровно символов b): принять
Все маркеры сняты: принять

Ответ: при . Два маркера на стек на каждое a; на каждое b снять один маркер; b на выход только для первичных маркеров; принять при пустоте стека в допустимом диапазоне.

4.6. Замкнутость класса языков DPDA по дополнению — идея построения (Лекция 7, Пример 1)

Объясните, почему класс языков DPDA замкнут по дополнению, и набросайте построение дополняющего DPDA.

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

Идея: дополнение языка DPDA строится так: (1) сделать DPDA ациклическим, (2) полностью определить , (3) поменять местами принимающие и непринимающие состояния.

  1. Почему не работает простой обмен состояний: на входе машина может оказаться в непринимающем , затем -перейти в принимающее . После обмена станет принимающим — «дополнение» тоже примет — ошибка.
  2. Шаг 1 — убрать циклы (ацикличность): преобразовать DPDA так, чтобы после полного чтения входа -продолжений не было; вычисление заканчивается в однозначном состоянии. Любой DPDA эквивалентен ациклическому (доказательство опускаем; нужно аккуратно убрать -циклы без смены языка).
  3. Шаг 2 — полнота : добавить непринимающее состояние ошибки и направить туда все неопределённые переходы. Тогда у каждой конфигурации ровно один преемник.
  4. Шаг 3 — обмен и : машина полна и ациклична после входа — одно финальное состояние; обмен корректно инвертирует принятие.
  5. Итог: дополняющий DPDA распознаёт , если исходный распознаёт . DPDA замкнут по .

Ответ: замкнутость по дополнению — трёхшаговое построение: ацикличность, полнота , обмен финальными/нефинальными.

4.7. Незамкнутость DPDA по разности — доказательство от противного (Лекция 7, Пример 2)

Докажите, что DPDA не замкнут по разности множеств ().

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

Идея: тождество и замкнутость по дополнение дают противоречие с незамкнутостью по пересечению.

  1. Предположим от противного: DPDA замкнут по .
  2. Тождество: для любых :
  3. Замкнутости: по дополнению . По предположению , значит для любых .
  4. Но мы доказали незамкнутость по (например ). Противоречие.
  5. Вывод: предположение неверно. DPDA не замкнут по .

Ответ: от противного через и дополнение: из незамкнутости по следует незамкнутость по .

4.8. Незамкнутость DPDA по объединению — контрпример (Лекция 7, Пример 3)

Покажите, что класс языков, распознаваемых DPDA, не замкнут по объединению, используя и .

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

Идея: и по отдельности в , но не распознаётся DPDA — детерминированная машина не может на фазе a готовиться сразу к двум вариантам числа b.

  1. : втолкнуть по одному на a, затем снимать по одному на b; принять при сверху после всех b. Стандартная конструкция.
  2. : втолкнуть два на каждое a, затем снимать по одному на b; принять при сверху.
  3. :
    • Читая , DPDA должен «закоммитить» стек под или символов b.
    • После a стек фиксирован; число a не перечитать.
    • Детерминированно нельзя одновременно подготовиться к и символам b.
    • Формально часто ссылаются на (Бар-Хиллель) и алгебраические приёмы.
  4. Вывод: , значит DPDA не замкнут по .

Ответ: объединение — свидетель незамкнутости по объединению.

4.9. FST — перевод всех строк над (Туториал 7, Пример 1)

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

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

Идея: все строки принимаются — достаточно одного принимающего состояния с петлями.

fst_upper start q0 q0 start->q0 q0->q0 a/A b/B

Односостоятельный FST: a→A, b→B

  1. Компоненты FST:
    • Состояния: ; начальное ;
    • Входной алфавит ; выходной
  2. Переходы (петли на ):
    • : прочитать a, записать A
    • : прочитать b, записать B
  3. Трассировка для :
    • a в : выход A, остаться в
    • b: выход B, остаться
    • a: выход A, остаться
    • Конец входа; → принято

Ответ: выход . Одно состояние (принимающее) с петлями и .

4.10. FST — перевод только строк без символов b (Туториал 7, Пример 2)

Постройте конечный преобразователь, принимающий строки без символов b, с переводом , . Строки с b отвергаются (перевод не определён).

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

Идея: стоковое непринимающее состояние после первого b.

fst_no_b start q0 q0 start->q0 q0->q0 a/A q1 q1 q0->q1 b/B q1->q1 a/ε b/ε

FST: только строки без символа b

  1. Состояния: (принимающее — b ещё не было), (сток — было b)
  2. Переходы:
    • : в сток
    • : в стоке без выхода
  3. Трассировка : остаёмся в , выход → принято, перевод
  4. Трассировка : → отвергнуто (перевод не определён)

Ответ: состояния , принимающее. Строки без b переводятся в «верхний регистр»; с b — отвергаются.

4.11. PDT — перевод (Туториал 7, Пример 3)

Постройте преобразователь с магазином для с переводом , , т.е. .

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

Идея: нужен стек для подсчёта и проверки символов b. FST не сосчитает произвольное .

pdt_upper start q0 q0 start->q0 q1 q1 q0->q1 a, Z₀/AZ₀, A q1->q1 a, A/AA, A q2 q2 q1->q2 b, A/ε, B q2->q2 b, A/ε, B q3 q3 q2->q3 ε, Z₀/Z₀, ε

PDT: перевод aⁿbⁿ в AⁿBⁿ

  1. Состояния: (старт), (a), (b), (принимающее)

  2. Алфавит стека:

  3. Переходы:

    От К Метка Смысл
    Первое a: втолкнуть , вывести A
    Ещё a: втолкнуть , вывести A
    Первое b: снять , вывести B
    Ещё b: снять , вывести B
    Только наверху: принять

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

    • (выход A)
    • (выход A)
    • (выход B)
    • (выход B)
    • — ПРИНЯТО

Ответ: . Стек считает a, затем сопоставляет b.

4.12. PDT — перевод (Туториал 7, Пример 4)

Постройте детерминированный преобразователь с магазином для с переводом (на выход только «-часть», без a).

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

Идея: на фазе a выводить . На фазе b выводить b на каждое снятие.

pdt_bn start q0 q0 start->q0 q0->q0 a, */A*, ε q1 q1 q0->q1 b, A/ε, b q1->q1 b, A/ε, b qf qF q1->qf ε, Z₀/Z₀, ε

PDT: перевод aⁿbⁿ в bⁿ

  1. Состояния: (a), (b), (принимающее)

  2. Переходы:

    От К Метка Смысл
    Первое a: втолкнуть , без выхода
    Ещё a: втолкнуть , без выхода
    Первое b: снять , вывести b
    Ещё b: снять , вывести b
    Стек пуст до маркера: принять, без выхода

  3. Трассировка для (3 a и 2 b — не в ; возьмём ):

    • Втолкнуть , (без выхода), затем два снятия с выходом b, увидеть → принять.
    • Выход: .

Ответ: . Стек считает a; выход только на фазе снятия.

4.13. PDT — перевод (Туториал 7, Пример 5)

Постройте DPDT для с переводом (поменять блоки местами).

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

Идея: на фазе вталкивания (a) выводить b, на фазе снятия (b) — a.

pdt_swap start q0 q0 start->q0 q0->q0 a, */A*, b q1 q1 q0->q1 b, A/ε, a q1->q1 b, A/ε, a qf qF q1->qf ε, Z₀/Z₀, ε

PDT: перевод aⁿbⁿ в bⁿaⁿ

  1. Состояния: (a), (b), (принимающее)

  2. Переходы:

    От К Метка Смысл
    Первое a: втолкнуть , вывести b
    Ещё a: втолкнуть , вывести b
    Первое b: снять , вывести a
    Ещё b: снять , вывести a
    Конец: принять

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

    • a: выход b, втолкнуть
    • a: выход b, втолкнуть
    • b: выход a, снять
    • b: выход a, снять
    • Вершина → принять. Выход: . ✓

Ответ: . На вталкивании — b, на снятии — a.

4.14. DPDA — построение для (Туториал 7, Пример 6)

Постройте DPDA, распознающий .

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

Идея: втолкнуть на каждое a, сопоставить b, затем принять любое положительное число c (на счётчик c стек не опирается).

dpda_abncm start q0 q0 start->q0 q1 q1 q0->q1 a, Z₀/AZ₀ q1->q1 a, A/AA q2 q2 q1->q2 b, A/ε q2->q2 b, A/ε q3 q3 q2->q3 c, Z₀/Z₀ q3->q3 c, Z₀/Z₀

DPDA для aⁿbⁿcᵐ

  1. Состояния: (старт), (a), (b), (c, принимающее)

  2. Переходы:

    От К Метка Смысл
    Первое a: втолкнуть
    Ещё a: втолкнуть
    Первое b: снять
    Ещё b: снять
    Первое c (сверху — a и b согласованы): фаза c
    Ещё c

  3. Принятие: принимающее; достижимо только при символов b против символов a и хотя бы одном c.

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

4.15. DPDA — построение для (Туториал 7, Пример 7)

Постройте DPDA, распознающий .

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

Идея: пропустить a (не фиксируют соотношение), затем считать b вталкиваниями, затем проверять c снятиями.

dpda_am_bnc_n start q0 q0 start->q0 q1 q1 q0->q1 a, Z₀/Z₀ q1->q1 a, Z₀/Z₀ q2 q2 q1->q2 b, Z₀/BZ₀ q2->q2 b, B/BB q3 q3 q2->q3 c, B/ε q3->q3 c, B/ε q4 q4 q3->q4 ε, Z₀/Z₀

DPDA для aᵐbⁿcⁿ

  1. Состояния: (старт), (a), (b), (c), (принимающее)

  2. Переходы:

    От К Метка Смысл
    Первое a: стек не менять
    Ещё a
    Первое b: втолкнуть
    Ещё b: втолкнуть
    Первое c: снять
    Ещё c: снять
    Сверху только : все b согласованы с c — принять

  3. Принятие: принимающее, достижимо -переходом при наверху.

Ответ: DPDA с (принимающее ) распознаёт .

4.16. Незамкнутость DPDA по пересечению — контрпример (Туториал 7, Пример 8)

Покажите, что для и , и сделайте вывод о незамкнутости DPDA по пересечению.

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

Идея: оба языка распознаются DPDA (примеры выше). Пересечение — , не КС-язык (Бар-Хиллель).

  1. Пересечение: (Строка в обоих языках тогда и только тогда, когда числа a, b и c совпадают.)
  2. Бар-Хиллель для : пусть язык КС; — константа. Возьмём . Любое разбиение с пересекает не больше двух групп символов. Накачка вверх () ломает равенство счётчиков. Противоречие. Значит , тем более .
  3. Вывод: , но . Следовательно DPDA не замкнут по .

Ответ: пересечение не КС-язык, значит не распознаётся DPDA. Незамкнутость по пересечению доказана.