Информатика · объяснение и практика

Лемма о накачке: разбиение выбирает противник, а степень выбираете вы

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

Синие фигурные скобки держат между собой оранжевый квадрат.

В теме Методы алгоритмов: углубление · Учебная карта

Главная мысль

Если язык регулярен, существует длина накачки, после которой каждое достаточно длинное слово допускает специальное разбиение с сохраняющей язык накачкой. Для опровержения нужно выбрать слово и показать провал для любого разрешённого разбиения, а не для одного удобного.

Метод и постановка

Запишите порядок выбора. Предположение о регулярности даёт некоторое неизвестное p. Вы выбираете слово языка длиной не меньше p. Затем возможное разбиение xyz должно удовлетворять |xy|≤p и |y|>0. После этого вы можете выбрать степень i≥0, для которой xyⁱz выпадает из языка. Разбиение нельзя назначать самостоятельно только потому, что так проще нарушить правило.

Удачное слово делает все допустимые варианты y однотипными. Для языка равного числа сначала идущих a, затем b, слово a^p b^p помещает весь префикс длины p в блок букв a. Поэтому любое допустимое непустое y состоит только из a. Такое геометрическое ограничение слова заменяет бесконечный разбор всех разбиений коротким общим аргументом.

Проверка и границы вывода

При степени ноль блок y удаляется. Число букв a уменьшается, число b остаётся p, и равенство нарушается. Размер y знать не нужно: достаточно его положительной длины. Это доказывает выпадение для любого разрешённого разбиения и завершает противоречие с необходимым свойством регулярного языка.

Лемма даёт необходимое условие, но не универсальный алгоритм доказательства регулярности. Неудачная попытка найти контрпример не доказывает существование конечного автомата. Для положительного вывода лучше предъявить автомат, регулярное выражение или другое достаточное построение. Также не переносите условия разбиения из леммы для регулярных языков в лемму для контекстно-свободных: там другое число частей и другие ограничения. В письменном доказательстве отдельно назовите выбранное слово, произвольное разбиение, общую форму накачиваемой части и выбранную степень.

Пример

Пусть p=5 для наглядной проверки и слово aaaaabbbbb. Разрешённый y может быть a, aa или другой непустой блок внутри первых пяти a. При удалении y останется от нуля до четырёх a и пять b.

Каждый вариант нарушает равенство количеств. Значение пять иллюстрирует рассуждение, но само доказательство использует произвольное p и потому исключает любой возможный конечный автомат.

От чтения к действию

А теперь — вы

Достаточно ли выбрать одно неудобное разбиение слова и показать его провал?

Частые вопросы

Почему p нельзя выбрать удобным числом в доказательстве?

Его задаёт предполагаемый автомат; аргумент должен работать для любого возможного p.

Накачка доказывает регулярность, если не нашлось ошибки?

Нет. Отсутствие найденного контрпримера не заменяет достаточного построения автомата.

Углублённый разбор

Накачка и нерегулярность простых длин

Даже над алфавитом из одной буквы язык может требовать бесконечной памяти. Для простых длин полезно выбрать степень накачки так, чтобы новая длина обязательно разложилась на два нетривиальных множителя.

Перед началом: Простое число; Кванторы леммы о накачке.

Выбор слова использует произвольную границу

Рассмотрим L={a^q:q простое}. Предположим регулярность и обозначим её неизвестную длину накачки через p≥1. Существует простое q>p, поэтому можно выбрать слово a^q. Здесь не нужно вычислять q эффективнее какого-либо алгоритма: для противоречия достаточно существования сколь угодно больших простых чисел.

Любое разрешённое разбиение xyz имеет накачиваемый блок y=aᵏ с 1≤k≤p. Положение блока внутри унарного слова не влияет на итоговую длину. Однако длину k выбирает не доказывающий, поэтому дальнейшая степень должна разрушать простоту при каждом таком k. Выбор одного удобного разбиения доказательства не завершает.

Умножение длины заменяет угадывание составного числа

После накачки с показателем i длина равна q+(i−1)k. Выберем i=q+1. Тогда новая длина равна q+qk=q(k+1). Оба множителя больше единицы: q простое, а k≥1. Значит, длина составная при любом допустимом разбиении, и полученное слово не принадлежит L. Это противоречит необходимому условию регулярности.

Показатель i может зависеть от выбранного слова и даже от разбиения; лемма требует сохранения языка для всех i≥0. Здесь удалось выбрать одно i для всех k, что делает аргумент особенно прозрачным. Пытаться ограничиться i=0 или i=2 необязательно: изменение на небольшую величину может случайно снова дать простое число.

Унарность не превращает условие в конечный автомат

У однобуквенного ДКА последовательность состояний после aⁿ в конце концов входит в цикл. Поэтому множество принимаемых длин в регулярном унарном языке в конечном итоге периодично. Простые длины не обязаны допускать такую конечную периодическую память. Доказательство накачкой уже установило невозможность и не требует отдельной теоремы о распределении простых.

Проверка конечных длин не способна доказать нерегулярность бесконечного языка: любой конечный набор слов распознаётся автоматом. В численном свидетельстве нужно проверять именно алгебру общего шага q+(i−1)k=q(k+1) и все допустимые k для выбранной иллюстрации. Общий вывод обеспечивает произвольность p и существование q>p, а не размер выполненного перебора.

Одна степень против всех разбиений

Условие. Для иллюстрации возьмите p=5 и простое q=7. Проверьте единую степень накачки для всех разрешённых длин y.

  1. Возможные длины блока равны k=1,2,3,4,5. Исходное слово a⁷ принадлежит языку простых длин и длиннее p.
  2. Выбираем i=q+1=8, так что добавляется семь дополнительных копий y. Новая длина равна 7+7k.
  3. Получаются 14,21,28,35,42. Все они делятся на семь и больше семи, поэтому ни одно не является простым.
  4. Общее доказательство заменяет числа 5 и 7 произвольными p и простым q>p. Формула произведения остаётся верной для каждого допустимого k.

Ответ. Язык простых длин нерегулярен; показатель q+1 даёт составную длину при любом разбиении.

Проверка. Точный перебор всех k≤5 и дополнительных простых q проверяет произведение и нетривиальность множителей; общий аргумент приведён для произвольного p.

Где легко ошибиться. Не пытайтесь доказать составность словами «длина увеличилась». Существенен явный нетривиальный делитель q, появившийся из выбранной степени накачки.

Проверьте понимание

Какой показатель i даёт длину q(k+1)?

Вопросы к этой главе

Нужно знать следующее простое после p?

Для логического доказательства достаточно любого простого больше p. Точный ближайший сосед и оценки промежутков между простыми не используются.

Почему нельзя проверить только пять разбиений?

Число пять относится к иллюстрации. В доказательстве p неизвестно, и рассматривается произвольная длина k от единицы до p с общей формулой составности.

Сверить определения и условия

Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.

  • Eric Blais: Nonregular Languages

    Прочитаны кванторы накачки и отдельный пример унарных степенных длин. Собственное доказательство для простых использует множитель q(k+1), а не промежуток между степенями; числовое свидетельство создано отдельно.

Нерегулярность через пересечение с регулярным языком

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

Перед началом: Замкнутость регулярных языков; Палиндром.

Противоречие строится через замкнутую операцию

Пусть R регулярный, а L∩R нерегулярный. Если бы L был регулярным, произведение автоматов для L и R распознавало бы их пересечение, что дало бы противоречие. Значит, L нерегулярен. Важны оба условия: регулярность фильтра и точное описание пересечения. Одного включения известного нерегулярного подъязыка в L недостаточно.

Последняя ошибка особенно распространена: универсальный язык Σ* регулярный, хотя содержит любой нерегулярный язык. Поэтому нужно получить именно нерегулярный результат операции, сохраняющей регулярность при предположении о L. Фильтр не обязан сам проверять трудную зависимость; его задача — убрать лишние формы слов и сделать эту зависимость видимой.

Фильтр оставляет один центральный разделитель

Возьмём язык всех палиндромов над {a,b} и R=a*ba*. Этот регулярный фильтр пропускает слова ровно с одной b. Его автомату достаточно помнить, встретилась ли b, и перейти в ловушку при второй b. Если слово aⁱbaʲ является палиндромом, число a слева и справа обязано совпадать. Обратно, каждое aⁿbaⁿ действительно читается одинаково в обе стороны.

Следовательно, пересечение точно равно {aⁿbaⁿ:n≥0}. Теперь накачка действует только в левом блоке a, если выбрать слово aᵖbaᵖ. Удаление любого непустого y из первых p букв уменьшает только левую часть. Правая остаётся длины p, и слово перестаёт принадлежать пересечению. Это доказывает его нерегулярность.

Разделяйте трудное свойство и простой формат

Фильтр R не проверяет равенство длин: он допускает все aⁱbaʲ с независимыми i,j. Нерегулярная связь возникает из требования палиндромности. Если незаметно включить равенство в описание R, доказательство станет круговым, потому что регулярность такого фильтра как раз неверна. Для каждого фильтра полезно предъявить автомат или регулярное выражение.

В проверяемом примере сравните три предиката: палиндромность, ровно одну b и равенство двух блоков. Их логическое соотношение должно выполняться на всех протестированных словах. Этот конечный тест подтверждает правильность описания пересечения; бесконечную нерегулярность доказывает отдельно рассуждение для произвольной длины накачки, а не перебор длин до выбранного предела.

Проверка фильтра и произвольного удаления

Условие. Для палиндромов L и фильтра R=a*ba* выпишите пересечение. На слове a⁴ba⁴ проверьте удаление блока y длины от одного до четырёх в начальном блоке.

  1. При ровно одной b палиндромность требует равного числа a по обе стороны. Поэтому L∩R={aⁿbaⁿ:n≥0}, включая слово b при n=0.
  2. Для p=4 слово aaaa baaaa имеет левый и правый блоки длины четыре. Пробел здесь лишь отделяет запись блоков и не принадлежит алфавиту.
  3. После удаления k букв a слева получаются длины (3,4),(2,4),(1,4),(0,4). Во всех случаях центральная b сохраняется, но палиндромность нарушается.
  4. Для произвольного p все допустимые y лежат в первых p буквах a и имеют k>0. Поэтому тот же аргумент доказывает нерегулярность пересечения и затем всего L.

Ответ. Палиндромы нерегулярны: регулярный фильтр выделяет нерегулярное равенство двух блоков.

Проверка. Перебор слов до длины девяти подтверждает точное описание пересечения; отдельная проверка всех начальных удалений подтверждает иллюстрацию при p=4.

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

Проверьте понимание

Чему равно пересечение палиндромов с a*ba*?

Вопросы к этой главе

Фильтр может быть конечным?

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

Можно использовать разность вместо пересечения?

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

Сверить определения и условия

Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.

  • Illinois CS/ECE374: Language Transformations

    Прочитана замкнутость регулярных языков относительно пересечения через произведение. Собственный фильтр ровно одной b и доказательство нерегулярности палиндромов разработаны отдельно.

Синтаксический моноид различает регулярность и отсутствие звезды

Звёздочка в удобной регулярной записи ещё не означает, что язык невозможно описать без неё. Алгебраический критерий смотрит на поведение всех слов в минимальном автомате. Сравним язык слов, оканчивающихся на a, и язык чётной длины: оба регулярны, но только первый имеет апериодический синтаксический моноид.

Перед началом: Минимальный детерминированный автомат; Композиция преобразований конечного множества.

Слово задаёт преобразование состояний

Каждое слово w переводит любое состояние ДКА в определённое состояние после чтения w. Такие преобразования замкнуты относительно композиции и содержат тождественное преобразование пустого слова. Для минимального ДКА этот моноид соответствует синтаксическому моноиду языка. Использовать произвольный автомат с лишними состояниями опасно: его ненужные циклы могут не характеризовать сам язык.

Конечный моноид апериодичен, если для каждого его элемента t последовательность степеней стабилизируется: t^n=t^(n+1) при некотором n. Недостаточно проверить только один генератор или только отсутствие самопетель на рисунке. Нужно учитывать все преобразования слов; условие относится к их степеням, ане к наличию графовых циклов вообще.

Без звезды не означает конечность языка

Звёздно-свободные выражения строятся из конечных языков с помощью объединения, конкатенации и дополнения относительно полного множества слов. Теорема Шютценберже связывает этот класс регулярных языков с апериодичностью синтаксического моноида. Здесь используется её формулировка; общее доказательство теоремы не подменяется маленьким примером.

Для Σ={a, b} язык слов, оканчивающихся на a, имеет минимальный автомат с двумя состояниями: последнее прочитанное a или отсутствие такого окончания. Буква a задаёт постоянное преобразование в принимающее состояние, b — постоянное к непринимающему. Вместе с тождественным преобразованием это все три элемента моноида; каждый идемпотентен. Язык бесконечен, но описывается(¬∅)·{a} без применения операции звезды.

Чётность создаёт нестабилизирующуюся перестановку

на односимвольном алфавите{a} язык чётной длины имеет два различимых достижимых состояния чётности. Преобразование одной буквы меняет их местами: T²=I, T³=T, и процесс чередуется бесконечно. Никакие соседние степени T не совпадают. Синтаксический моноид содержит нетривиальную группу порядка 2, значит, он не апериодичен, а язык не звёздно-свободен.

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

Три идемпотента против двухэлементной группы

Условие. Сравните L1 — слова над{a, b}, оканчивающиеся на a, и L2 — слова чётной длины над{a}. Вычислите преобразования минимальных автоматов и примените критерий апериодичности.

  1. Для L1 пустое слово даёт I, непустое слово заканчивается a либо b и даёт постоянное A либо B. Иных преобразований нет.
  2. I²=I, A²=A, B²=B. Все три элемента стабилизируются, поэтому моноид L1 апериодичен.
  3. Для L2 преобразования равны I, T, где T меняет две чётности местами. Степени T чередуются между T и I.
  4. По теореме Шютценберже L1 звёздно-свободен, а L2 нет. Для L1 явное выражение(¬∅)·{a} подтверждает вывод.

Ответ. L1: апериодический моноид из 3 элементов. L2: группа порядка 2, неапериодична. Регулярность есть у обоих языков.

Проверка. Оба автомата минимальны: два состояния достижимы и различаются принятием пустого продолжения. Композиция трёх преобразований L1 остаётся среди I, A, B; у L2 замкнутая таблица даёт T·T=I.

Где легко ошибиться. Проверяйте синтаксический моноид или преобразования минимального ДКА, ане случайные дополнительные состояния другой реализации.

Проверьте понимание

Почему язык L2 не звёздно-свободен?

Вопросы к этой главе

Может ли звёздно-свободный язык быть бесконечным?

Да. Дополнение позволяет получить полный язык как¬∅, после чего конкатенация задаёт бесконечные классы без операции звезды.

Достаточно ли увидеть звезду в написанном регулярном выражении?

Нет. Вопрос состоит в существовании другого выражения без звезды. Выбранная удобная запись не доказывает, что такая операция неизбежна.

Сверить определения и условия

Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.

  • Manfred Kufleitner2014: Star-Free Languages and Local Divisors, §1–2

    Определения звёздно-свободности, апериодичности иформулировка теоремы Шютценберже. Два минимальных автомата, их моноиды иявное выражение L1 разобраны самостоятельно.

CYK распознаёт контекстно-свободное слово по интервалам

Нерегулярность языка не означает, что принадлежность конкретного слова нельзя проверить алгоритмом. CYK хранит для каждого интервала множество нетерминалов, способных породить его целиком. Разберём aabb по бинарной грамматике и отделим наличие вывода от числа возможных деревьев.

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

В ячейке хранится не символ ответа, а множество причин

Непустое слово и грамматика с правилами A→BC либо A→a, без ε-правил и единичных A→B. В выбранном соглашении старт может встречаться справа.

Для слова длины n обозначим T[i,j) множество нетерминалов, порождающих подстроку с позиции i до j−1. Сначала заполняют интервалы длины один по терминальным правилам A→a. Если несколько нетерминалов выводят ту же букву, в ячейку входят все они. Пустое множество означает отсутствие подходящего вывода для данного интервала.

Далее рассматривают длины два, три и так до n. Для каждого разреза i<k<j и правила A→BC добавляют A, если B∈T[i,k),C∈T[k,j). Нельзя соединять произвольные найденные подстроки: они должны без пропуска и перекрытия покрывать именно текущий интервал. Условие приёма всего слова — наличие старта S в T[0,n).

Почему все бинарные деревья охвачены

Любой нетерминальный корень вывода непустого интервала длины больше одного использует некоторое правило A→BC. Левое и правое поддеревья занимают два соседних непустых интервала, значит между ними есть один из перебираемых разрезов. Индукция по длине интервала доказывает, что таблица найдёт оба дочерних вывода и затем A.

Обратное направление тоже необходимо: добавленный A действительно имеет вывод из двух уже доказанных дочерних выводов. Для восстановления дерева сохраняют правило и разрез, вызвавшие добавление. Один такой указатель даёт одно дерево, но не доказывает отсутствия других. Обычное множество нетерминалов забывает, сколькими способами каждый из них получен.

Нормальная форма является условием рекурсии

Правила с длинной правой частью предварительно разбивают на бинарные. Единичные цепочки и ε-выводы требуют отдельной обработки, иначе простая инициализация пропустит допустимые случаи. Пустое слово не имеет ячейки положительной длины и проверяется отдельно по nullable-свойству стартового символа, а не чтением T[0,0).

В нашей грамматике нет ε, поэтому допускается S справа. Если учебное определение нормальной формы запрещает это, вводят новый старт и копируют к нему правые части правил S, сохраняя нужный язык. Для фиксированной бинарной грамматики число пар границ и разрезов имеет порядок O(n³); память таблицы — O(n²) множеств ограниченного размера.

aabb из бинарных правил

Условие. Грамматика: S→AB|AC, C→SB, A→a, B→b. Старт S. Заполните существенные ячейки для aabb, позиции 0,…,3.

  1. Односимвольные ячейки равны {A},{A},{B},{B}. Для ab в позициях [1,3) правило S→AB добавляет S.
  2. Интервалы aa и bb длины два не выводятся: правил для AA и BB нет. Поэтому их множества пусты.
  3. В интервале abb=[1,4) разрез после ab даёт S из [1,3) и B из [3,4). Правило C→SB добавляет C; других подходящих корней нет.
  4. Для всего aabb разрез после первой a даёт A и C. По S→AC получаем S∈T[0,4), следовательно, слово принимается.
  5. Указатели восстанавливают S⇒AC⇒aC⇒aSB⇒aABB⇒aabb. В исходной форме это обычный шаг aSb с последующим базовым S⇒ab.

Ответ. Слово принимается; T[1,3)={S}, T[1,4)={C}, T[0,4)={S}.

Проверка. Правила S описывают либо ab, либо aSb, поэтому язык равен {aᵏbᵏ:k≥1}. Это независимое описание подтверждает результат для aabb; aaabb не принимается из-за разных размеров блоков.

Где легко ошибиться. Не смешивайте номер начальной позиции с длиной интервала и не считайте одну сохранённую причину доказательством однозначности грамматики. CYK в форме множеств отвечает на вопрос существования вывода.

Проверьте понимание

Какое множество находится в T[1,4) для abb внутри разобранного aabb?

Вопросы к этой главе

Почему нельзя напрямую подать A→BCD в эту рекурсию?

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

CYK доказывает, что язык регулярный?

Нет. Он распознаёт отдельные слова контекстно-свободной грамматики, которая может описывать нерегулярный язык. Для нашей грамматики неограниченное равенство числа a и b сохраняется, несмотря на конечную таблицу для каждого заданного слова.

Сверить определения и условия

Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.

  • UMBC CMSC 451: Lecture 24, CYK algorithm for CFGs

    Прочитаны терминальная и бинарная группы правил, интервальная рекурсия и сохранение указателей дерева. Наши грамматика и aabb заданы самостоятельно; множество достижимых нетерминалов не используется как доказательство однозначности.

Источники и работа с материалом

Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.

Продолжить разбираться