Автоматы и границы алгоритмического доказательства
Детерминизация, различимость префиксов, накачка и неразрешимость семантических свойств программ.
Задачи модуля
Постройте ДКА из ε-НКА и проверьте короткие слова. Затем выясните, когда состояния действительно различаются будущим поведением, а не только именами.
Накачка и теорема Райса задают отрицательные результаты в разных моделях. Для их применения важны порядок кванторов и точное описание класса объектов.
Вычислять ε-замыкания и принимать слово по существованию успешного пути.
Доказывать нижнюю границу числа состояний различающими суффиксами.
Применять накачку для всех разбиений и отличать семантическое свойство от синтаксического.
Автоматы и разрешимость
Минимизация DFA: различающее продолжение как свидетель
Два состояния нельзя объединить, если существует продолжение слова, которое из одного приводит к принятию, а из другого к отказу. Такое продолжение является коротким сертификатом различимости.
Перед началом: Детерминированный автомат; Остаток числа.
Сравнивайте будущие языки состояний
Состояние DFA описывает всю информацию о прочитанном префиксе, необходимую для дальнейшего принятия. Два состояния эквивалентны, если для любого продолжения результат одинаков. Если найдётся хотя бы одно различающее слово, они обязаны остаться разными в минимальном автомате. Пустое продолжение тоже допустимо: принимающее и непринимающее состояния различимы немедленно. Поэтому похожие исходящие стрелки не являются достаточным основанием для слияния.
Достижимость нужна перед минимизацией
Недостижимое состояние не влияет на язык из начального и может быть удалено. Чтобы доказать минимальность автомата с k состояниями, достаточно показать достижимость каждого и попарную различимость. Первый пункт подтверждается префиксами, второй — продолжениями. Это конечный сертификат для конкретного автомата. Алгоритмы разбиения классов находят те же различия систематически: начинают с принимающих и остальных, затем уточняют классы по переходам до неподвижной точки.
Числовой остаток имеет операционный смысл
При чтении двоичного числа слева направо добавление бита b меняет остаток r по модулю m на (2r+b) mod m. Поэтому m остатков дают автомат делимости. Но число состояний такой конструкции не всегда следует объявлять минимальным без доказательства различимости. В нашей маленькой задаче все свидетели короткие, и таблица переходов проверяется обычной арифметикой. Соглашение о пустом слове и ведущих нулях нужно указать отдельно, поскольку оно меняет язык, хотя рекурсия остатков остаётся той же.
Различающее продолжение применяется к состояниям после уже прочитанных префиксов. Эти префиксы могут иметь разную длину: требование сравнивает будущие возможности, а не время достижения состояний.
Делимость двоичной записи на три
Условие. DFA имеет состояния 0,1,2, старт и единственное принимающее 0, переход r→(2r+b) mod3. Пустое слово принимается. Докажите минимальность.
0 отличается от 1 и 2 пустым продолжением, потому что только 0 принимает.
Для пары 1,2 продолжение 1 даёт переходы соответственно в 0 и 2.
Одна ветвь принимает, другая нет; все три достижимых состояния попарно различимы.
Ответ. Автомат минимален и требует три состояния.
Проверка. Таблица переходов по 0: [0,2,1], по 1: [1,0,2]; она подтверждает все предъявленные свидетели.
Где легко ошибиться. Нельзя доказывать минимальность только отсутствием одинаковых строк в исходной таблице переходов: эквивалентность определяется всеми продолжениями.
Проверьте понимание
Вопросы к этой главе
Может ли различающее слово быть пустым?
Да. Это самый короткий свидетель для пары принимающего и непринимающего состояний.
Почему нужны достижимые состояния?
Недостижимые можно удалить без изменения языка из старта, поэтому они не дают нижнюю границу минимального размера.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
Конечные автоматы, эквивалентность состояний и различающие продолжения. Проверены релевантные определения и условия, а не прочитан весь учебник. Условия задач и расчёты главы подготовлены отдельно.
Детерминизация NFA: пустое подмножество тоже состояние
После чтения префикса недетерминированный автомат может находиться сразу в нескольких состояниях или ни в одном. Метод подмножеств хранит весь этот набор, включая пустой, чтобы переходы DFA оставались определёнными.
Перед началом: Множества; Недетерминированный автомат.
Объединяйте все возможные переходы
Состояние детерминированного автомата — множество состояний NFA, достижимых после текущего слова. По символу берут объединение переходов из каждого элемента. Если присутствуют ε-переходы, до и после чтения символа дополнительно учитывают ε-замыкание. В этой главе их нет, поэтому стартовое множество содержит только старт NFA. Множество принимающее тогда и только тогда, когда содержит хотя бы одно принимающее состояние исходного автомата.
Пустое множество означает окончательную потерю ветвей
Если ни одна активная ветвь не имеет нужного перехода, возникает ∅. Для полного DFA из него по любому символу снова идём в ∅. Пропуск этого состояния без явной модели частичного автомата оставляет таблицу незавершённой. При этом не нужно создавать все 2ⁿ подмножеств заранее: обход от стартового набора строит только достижимые. Экспоненциальная верхняя граница возможна в худшем случае, но конкретный автомат часто использует намного меньше наборов.
Инвариант доказывает равенство языков
После каждого префикса набор DFA должен в точности совпадать с активными состояниями NFA. Это доказывается индукцией по длине слова: база — старт, переход — объединение всех следующей возможностей. Принимающее условие затем немедленно сохраняет язык. Проверка нескольких слов полезна, но не заменяет этот общий инвариант. В маленьком примере независимый симулятор множества ветвей позволяет проверить всю таблицу и отдельно убедиться, что пустой набор действительно достижим.
Четыре достижимых набора
Условие. NFA: старт q₀, принимает q₁. Переходы q₀ по a в {q₀,q₁}, по b в ∅; q₁ по a в ∅, по b в {q₁}.
Обозначим A={q₀}, B={q₀,q₁}, C={q₁}, D=∅.
Из A по a идём в B, по b в D.
Из B по a идём в B, по b в C; из C по a в D, по b в C.
D замкнуто по обоим символам. Принимают B,C; все четыре набора достижимы словами ε,a,ab,b.
Ответ. Детерминизация имеет четыре достижимых состояния A,B,C,D с указанной таблицей.
Проверка. Слово aab принимается, b отвергается; прямое развитие ветвей NFA даёт те же наборы после каждого символа.
Где легко ошибиться. Принимающим считается набор с хотя бы одним принимающим элементом, а не только набор, состоящий исключительно из принимающих состояний.
Проверьте понимание
Вопросы к этой главе
Можно ли не хранить ∅?
В частичном автомате можно считать отсутствующий переход отказом, но тогда нужно явно изменить соглашение о полноте таблицы.
Обязательно ли все подмножества достижимы?
Нет. Их достижимость определяется переходами исходного автомата и стартовым состоянием.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
Построение DFA по множествам состояний, принимающие множества и пустой набор. Проверены релевантные определения и условия, а не прочитан весь учебник. Условия задач и расчёты главы подготовлены отдельно.
Производная регулярного выражения: остаточный язык после символа
Производная регулярного выражения по символу описывает допустимый остаток слова после его прочтения. Последовательное вычисление производных превращает проверку принадлежности в вопрос о пустом слове.
Перед началом: Регулярное выражение; Конкатенация языков.
Производная удаляет один заданный символ слева
Для языка L определим D_aL={w:aw∈L}. У объединения производная распределяется по ветвям. У произведения XY получаем D_a(X)Y и дополнительно D_a(Y), если X содержит пустое слово. Это дополнительное слагаемое существенно: прочитанный символ мог относиться уже к правому множителю. У звезды D_a(X*)=D_a(X)X*. Пустой язык и язык из пустого слова различаются: первый ничего не принимает, второй принимает только отсутствие дальнейших символов.
Nullable отвечает на конечный вопрос
После обработки всех символов w исходное выражение принимает w тогда и только тогда, когда полученный остаточный язык содержит ε. Это свойство называется nullable. Для объединения оно вычисляется через «или», для конкатенации через «и», звезда всегда nullable. Само отсутствие букв в печатном виде ещё не доказывает nullable: например, пустой язык тоже может быть обозначен одним служебным символом. Алгебраическое упрощение должно сохранять язык, а не только сокращать запись.
Остаточные выражения можно объединять
Разные синтаксические выражения способны описывать один язык. Если сохранять их без нормализации, представление производных будет избыточным. Это вопрос эффективности, а не определения языка. Связь с автоматами возникает, когда остаточные языки рассматриваются как состояния. В ручной проверке полезно сопоставить производные с прямым разбиением слова на допустимые части выражения. Такой независимый маршрут позволяет обнаружить пропущенное nullable-слагаемое, особенно при звезде слева от конкатенации.
После чтения неподходящего символа может возникнуть пустой язык, и все последующие производные останутся пустыми. Это аналог поглощающего отвергающего состояния автомата, а не язык из пустого слова, который ещё принимает завершение.
Четыре символа до пустого остатка
Условие. Пусть r=a*b(a|b). Проверьте слова aabb и aab через производные.
Производная r по a снова равна r: звезда поглощает начальную a, а правая часть начинается с b.
После двух a остаток по-прежнему a*b(a|b).
После следующего b остаток равен a|b, который не nullable. Поэтому слово aab отвергается.
Ещё одна b превращает остаток в ε, который nullable; aabb принимается.
Ответ. aabb принадлежит языку, aab не принадлежит.
Проверка. Прямое описание языка требует несколько a, затем b и ровно один заключительный символ a или b; оба результата совпадают.
Где легко ошибиться. При производной произведения нельзя забывать правый вклад, если левый множитель допускает пустое слово.
Проверьте понимание
Вопросы к этой главе
Производная здесь числовая?
Нет. Это операция над языками по прочитанному символу; название связано с алгебраическими правилами, а не с пределом отношений.
Почему a|b не nullable?
Обе ветви требуют один символ, поэтому пустое продолжение не подходит.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
§3.1–3.2: производные языка, nullable и правила произведения и звезды. Проверены релевантные определения и условия, а не прочитан весь учебник. Условия задач и расчёты главы подготовлены отдельно.
Лемма о накачке: кто выбирает разбиение
Доказательство нерегулярности нельзя строить на одном удобном разбиении слова. Противник вправе выбрать любое допустимое разбиение, поэтому контрход должен работать для каждого из них.
Перед началом: Регулярный язык; Порядок кванторов.
Запишите порядок выбора
Если язык регулярен, существует длина p, после которой каждое достаточно длинное слово языка допускает разбиение xyz с |xy|≤p, |y|>0 и xyⁱz в языке при всех i≥0. Для опровержения нужно для любого предполагаемого p выбрать слово, затем рассмотреть любое допустимое разбиение и найти хотя бы один показатель i, выводящий слово из языка. Выбор разбиения не принадлежит доказывающему нерегулярность. Этот порядок ходов является содержанием метода, а не формальной мелочью.
Ограничение первых p символов локализует повтор
У языка {aⁿbⁿ:n≥0} выбирают слово aᵖbᵖ. Так как |xy|≤p, непустая часть y состоит только из a. Её точная длина неизвестна, но положительна. Накачка меняет число a, не меняя число b, поэтому равенство нарушается. Достаточно одного общего выбора i=0 для всех допустимых разбиений. Подробное перечисление мест начала y не требуется, потому что аргумент зависит только от её алфавита и ненулевой длины.
Лемма даёт необходимое, а не достаточное условие
Неудача найти контрпример не доказывает регулярность. Для положительного результата лучше построить автомат или регулярное выражение. Кроме того, есть нерегулярные языки, для которых простая форма накачки неудобна; тогда используют различающие продолжения или другие теоремы. Конечная проверка нескольких p иллюстрирует аргумент, но не заменяет доказательство для произвольного p. В нашем worked отдельно приводится общий символический вывод и лишь затем конкретная численная иллюстрация.
Непустота y обязательна: при y=ε накачка ничего не меняла бы и не могла бы выявить противоречие.
Любое разбиение при p=4
Условие. Для слова aaaabbbb покажите сбой накачки при любом разбиении с |xy|≤4 и |y|>0; затем обобщите.
Часть y целиком состоит из a и имеет длину k∈{1,2,3,4}.
При i=0 удаляется y, остаётся a^(4−k)b⁴.
Числа символов различаются для каждого допустимого k, значит слово вне языка.
При произвольном p тот же расчёт даёт a^(p−k)bᵖ с 1≤k≤p; противоречие универсально.
Ответ. Язык {aⁿbⁿ} нерегулярен; выбор i=0 ломает любое допустимое разбиение выбранного слова.
Проверка. Для p=4 перебор всех пар границ x,y подтверждает, что y содержит только a; общий аргумент использует лишь неравенства длин.
Где легко ошибиться. Показ одного плохого разбиения не опровергает лемму: регулярный язык обязан иметь хотя бы одно хорошее, а не все хорошие.
Проверьте понимание
Вопросы к этой главе
Можно ли выбрать i после разбиения?
Да. Для опровержения допускается контрход, зависящий от разбиения; здесь даже один i=0 работает для всех.
Почему слово обязательно принадлежит языку?
Лемма применяется к словам самого языка. Взять постороннее слово и получить отказ ничего не доказывает.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
Формулировка pumping lemma и порядок кванторов; общий аргумент и конечная иллюстрация разделены. Проверены релевантные определения и условия, а не прочитан весь учебник. Условия задач и расчёты главы подготовлены отдельно.
Сведение к остановке: направление определяет вывод
Чтобы доказать неразрешимость новой задачи, нужно превратить известную неразрешимую задачу в неё. Обратное преобразование показывает лишь, что новая задача не труднее старой, и не даёт нужного противоречия.
Перед началом: Алгоритмическая разрешимость; Описание программы.
Предположите решатель целевой задачи
Пусть A — известная неразрешимая задача, B — исследуемая. Для сведения A≤B строят вычислимое преобразование входа x в f(x) с эквивалентностью x∈A тогда и только тогда f(x)∈B. Если бы B имела всюду останавливающийся решатель, композиция с f решала бы A. Противоречие переносит неразрешимость. Преобразование обязано завершаться для любого входа, а не ждать результата той самой потенциально бесконечной программы.
Обёртка может быть построена без исполнения
Рассмотрим вопрос, выдаст ли программа когда-нибудь специальную метку. По паре описания M и входа w создают новую программу P: симулировать M(w), а после её остановки вывести метку. Построение P — конечная работа с описанием. Оно не требует узнать заранее, остановится ли M. Если M не остановится, P продолжит симуляцию и ничего не выведет; если остановится, метка появится. Так совпадают ответы на исходный и целевой вопросы.
Полурешение не является решением
Запуск P и ожидание метки подтверждает положительные случаи, но на отрицательных может ждать бесконечно. Это распознавание, а не всюду завершающийся решатель. Ограниченный симулятор на фиксированное число шагов решает другую, конечную задачу и не опровергает неразрешимость неограниченной. В учебном доказательстве не требуется запускать произвольный код: достаточно точно описать преобразование и доказать оба направления эквивалентности. Безопасная проверка может использовать только конечные символические трассы.
Метка выбирается так, чтобы симулятор не выдавал её самопроизвольно: его внутренний вывод подавляется, а целевой внешний вывод выполняется только после завершения симуляции.
Метка после остановки
Условие. Сведите HALT(M,w) к вопросу PRINT(P,#): выведет ли P когда-нибудь #.
По конечным текстам M,w строим текст P, содержащий симулятор и команду вывода после завершения симуляции.
Если M(w) останавливается через k шагов, P завершит симуляцию и выведет #.
Если M(w) не останавливается, выполнение не достигнет команды вывода.
Предполагаемый полный решатель PRINT дал бы полный решатель HALT, что невозможно.
Ответ. HALT≤PRINT, поэтому PRINT неразрешима в этой неограниченной модели.
Проверка. Обе ветви доказаны без запуска M. Само построение P конечно и не зависит от знания k.
Где легко ошибиться. Сведение PRINT≤HALT не доказывало бы неразрешимость PRINT: разрешимая задача тоже может сводиться к более трудной.
Проверьте понимание
Вопросы к этой главе
Почему симуляция не делает преобразование бесконечным?
Преобразование только записывает программу с симулятором. Бесконечность может возникнуть позже при её исполнении.
Можно ли проверить тысячу шагов?
Да, но это решает только ограниченную версию. Отсутствие остановки за тысячу шагов не означает отсутствие остановки вообще.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
Сведения и неразрешимость остановки; обёртка описана без исполнения произвольного кода. Проверены релевантные определения и условия, а не прочитан весь учебник. Условия задач и расчёты главы подготовлены отдельно.
Связанные методы
Один шаг ДКА хранит сразу все возможные состояния НКА
Состояние детерминированного автомата — множество возможных состояний исходного НКА. Перед чтением и после каждого символа добавляют ε-замыкание. Подмножество принимающее, когда в нём существует хотя бы одно принимающее состояние НКА.
Два префикса различимы, если существует общее продолжение, после которого ровно одно из двух слов принадлежит языку. Такие префиксы не могут приводить ДКА в одно состояние. Набор из k попарно различимых префиксов требует как минимум k состояний.
Лемма о накачке: разбиение выбирает противник, а степень выбираете вы
Если язык регулярен, существует длина накачки, после которой каждое достаточно длинное слово допускает специальное разбиение с сохраняющей язык накачкой. Для опровержения нужно выбрать слово и показать провал для любого разрешённого разбиения, а не для одного удобного.