Лемма о накачке для регулярных языков

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

Лемма о накачке впервые сформулировал Иешуа Бар-Хиллель, Перлес и Шамир в 1961 году. Она полезна для опровержения регулярности заданного языка. Она является одной из нескольких лемм о накачке, у каждой из которых похожее предназначение.

Формальное утверждение

Пусть L регулярный язык. Тогда существует целое p ≥ 1 зависящее только от L, такое что строки w из L длины по меньшей мере p (p называется «длиной накачки») может быть записано как w = xyz, так что:

1. |y| ≥ 1
2. |xy| ≤ p
3. для всех i ≥ 0, xyⁱz ∈ L

y — это подстрока, которую можно накачать (удалить или повторить произвольное число раз, так что результат останется в L). (1) означает, что цикл y должен быть накачан хотя бы длиной 1, (2) означает, что цикл должен быть в пределах первых p символов. На x и z ограничений не накладывается.

<math>\forall L\subseteq \Sigma^* (\mbox{regular}(L) \Rightarrow (\exists p\geq 1 (\forall w \in L ((|w|\geq p) \Rightarrow (\exists x,y,z \in \Sigma ^* (w=xyz \Rightarrow (|y|\geq 1 \and |xy|\leq p \and \forall i\geq 0 (xy^iz\in L))))))))</math>

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

Лемма о накачке описывает существенное свойство регулярных языков. Она утверждает, что слово w языка L длины по меньшей мере m, (где m константа, называемая длиной накачки, зависит лишь от L) можно разделить на три подстроки, <math>w = xyz</math>, так что среднюю часть, y (непустую), можно повторить произвольное число раз (включая ноль, то есть удалить) и получить строку из L. Этот процесс повторения называется «накачкой». Более того, лемма о накачке гарантирует, что длина xy не превысит m, ограничивая способы разделения строки w. Заметим, что конечные языки удовлетворяют требованиям леммы о накачке тривиально определяя m длиной максимальной строки из языка плюс один.

Использование леммы

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

Например нерегулярность языка L = {aⁿbⁿ : n ≥ 0} над алфавитом Σ = {a, b} можно показать следующим образом. Пусть w, x, y, z, p, и i заданы соответственно формулировке леммы выше. Пусть w из L задаётся как w = a^pb^p. По лемме о накачке, существует разбиение w = xyz, где |xy| ≤ p, |y| ≥ 1, такое что xyⁱz принадлежит L для любого i ≥ 0. Если допустить, что |xy|=p, а |z|=p, то xy — это первая часть w, состоящая из p последовательных экземпляров символа a. Поскольку |y| ≥ 1, она содержит по меньшей мере одну букву a, а xy²z содержит больше букв a чем b. Следовательно, xy²z не в языке L (заметим, что любое значение i ≠ 1 даст противоречие). Достигнуто противоречие, поскольку в этом случае накачанное слово не принадлежит языку L. Следовательно предположение о регулярности L неверно. Следовательно L — не регулярный язык.

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

Доказательство леммы о накачке

Для каждого регулярного языка существует конечный автомат (КА), принимающий этот язык. Если язык конечен, то результат можно получить немедленно, просто задав длину накачки p более длины самого длинного слова языка: в это случае нет ни одной строки в языке длиннее p, и утверждение леммы выполняется безусловно.

Если регулярный язык бесконечен, то существует минимальный КА, его принимающий. Число состояний этого КА и принимается за длину накачки p. Если длина строки превышает p, то хотя бы одно состояние при обработке строки повторяется (назовём его S). Переходы из состояния S и обратно соответствуют некоторой строке. Эту строку обозначим y по условиям леммы, и поскольку автомат примет строку как без части y, так и с повторяющейся частью y, условия леммы выполнены.

Проще понять доказательство, обратившись к примеру. На следующей диаграмме показан КА.

Файл:An automat accepting the language a(bc)*d.png

Этот КА принимает строку abcbcd. Поскольку длина её превышает число состояний, существуют повторяющиеся состояния. В этом примере повторяются состояния q1 и q2. Поскольку подстрока bcbc строки abcbcd проводит автомат по переходам из состояния q1 обратно в q1, эту строку можно повторять сколько угодно раз, и КА всё равно будет её принимать, например строки abcbcbcbcd и ad. В терминах леммы о накачке, строка abcbcd разбивается на часть x=a, часть y=bc и часть z=bcd. (Заметим, что можно разбить её различными способами, например x=a, y=bcbc, z=d, и все условия будут выполнены, кроме |xy| ≤ p).

Обобщённая лемма о накачке для регулярных языков

Если язык L регулярен, то существует число p > 0 (длина накачки), такое что для любой строки uwv из L с |w| ≥ p справедливо представление

uwv = uxyzv

где x, y и z — строки, такие что |xy| ≤ p, |y| > 0 и

uxyⁱzv принадлежит L для любого целого i ≥ 0.

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

Недостаточность леммы

Заметим, что ни исходная, ни обобщённая леммы о накачке не дают достаточного условия регулярности языка. Так, существуют нерегулярные языки, для которых лемма выполнена. Если лемма не выполняется для некоторого языка L, то L нерегулярен. Если лемма выполняется для L, то L может быть регулярным.

Например, язык L = {uvwxy : u, y <math>\in</math> {0,1,2,3}^*, vwx <math>\in</math> {0,1,2,3}∧(v=w∨v=x∨x=w)} <math>\cup</math> {w : w <math>\in</math> {0,1,2,3}^* и ровно 1/7 символов из w являются 3} (то есть L содержит все строки над алфавитом {0,1,2,3}, содержащих подстроки длины 3, в которых есть повторяющийся символ, и те строки, в которых ровно 1/7 символов являются 3), не является регулярным, но тем не менее может быть «накачан» при p = 5. Предположим некоторая строка s имеет длину не меньше 5. Тогда, поскольку в алфавите только 4 символа, по крайней мерее два из 5 символов строки совпадают, а между ними лежат не более 3 символов.

• Если одинаковые символы разделены 1 или 0 символами, накачаем один из двух других символов строки, что не повлияет на строку, содержащую дубликаты.
• Если одинаковые символы разделены 2 или 3 символами, накачаем 2 из символов, разделяющих их. Накачивание любого из них вниз или вверх приведёт к созданию подстроки длины 3, содержащей 2 повторяющихся символа.
• Вторым условием языка L достигается его нерегулярнсть, то есть существует бесконечное число строк, которые содержатся в L, но не могут быть получены накачиванием меньшей строки из L.

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

Ссылки

• Introduction to the Theory of Computation. — PWS Publishing, 1997. — ISBN 0-534-94728-X Section 1.4: Nonregular Languages, pp. 77—83.
• John E. Hopcroft and Jeffrey D. Ullman, Introduction to Automata Theory, Languages and Computation, Addison-Wesley Publishing, Reading Massachusetts, 1979. ISBN 0-201-02988-X. (See chapter 3.)