Лемма о накачке для обычных языков

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

В частности, лемма о накачке говорит, что для любого регулярного языка $L\; \{\backslash \; displaystyle\; L\}$существует константа $p\; \{\backslash \; displaystyle\; p\}$такое, что любое слово $w\; \{\backslash \; displaystyle\; w\}$в $L\; \{\backslash \; displaystyle\; L\}$длиной не менее $p\; \{\backslash \; displaystyle\; p\}$можно разделить на три подстроки, $w\; =\; xyz\; \{\backslash \; displaystyle\; w\; =\; xyz\}$, где средняя часть $y\; \{\backslash \; displaystyle\; y\}$не должно быть пустым, например, слова $xz,\; xyz,\; xyyz,\; xyyyz,...\; \{\backslash \; displaystyle\; xz,\; xyz,\; xyyz,\; xyyyz,...\}$, построенный путем повторения $y\; \{\backslash \; displaystyle\; y\}$ноль или более раз все еще в $L\; \{\backslash \; Displaystyle\; L\}$. Этот процесс повторения известен как «накачивание». Кроме того, лемма о накачке гарантирует, что длина $xy\; \{\backslash \; displaystyle\; xy\}$будет не более $p\; \{\backslash \; displaystyle\; p\}$, что накладывает ограничение на способы, которыми $w\; \{\backslash \; displaystyle\; w\}$может быть разделен. Конечные языки пусто удовлетворяют лемме перекачки, имея $p\; \{\backslash \; displaystyle\; p\}$, равную максимальной длине строки в $L\; \{\backslash \; displaystyle\; L\}$плюс один.

Лемма о перекачке полезна для опровержения регулярности конкретного рассматриваемого языка. Впервые это было доказано Майклом Рабином и Даной Скотт в 1959 году, а вскоре вновь обнаружено Иегошуа Бар-Хиллелем, Мишей А. Перлес и Эли Шамир в 1961 году, как упрощение их леммы о перекачке для контекстно-свободных языков.

• 1 Формальное утверждение
• 2 Использование леммы
• 3 Доказательство леммы о накачке
• 4 Общая версия леммы о накачке для регулярных языков
• 5 Обратное к лемме неверно
• 6 См. Также
• 7 Примечания
• 8 Ссылки

Пусть $L\; \{\backslash \; displaystyle\; L\}$будет обычным языком. Тогда существует целое число $p\; \ge \; 1\; \{\backslash \; displaystyle\; p\; \backslash \; geq\; 1\}$, зависящее только от $L\; \{\backslash \; displaystyle\; L\}$такое, что каждая строка $w\; \{\backslash \; displaystyle\; w\}$в $L\; \{\backslash \; displaystyle\; L\}$длиной не менее $p\; \{\backslash \; displaystyle\; p\}$($p\; \{\backslash \; displaystyle\; p\}$называется «длина накачки») может быть записано как $w\; =\; xyz\; \{\backslash \; displaystyle\; w\; =\; xyz\}$(т. Е. $w\; \{\backslash \; displaystyle\; w\}$можно разделить на три подстроки), удовлетворяющие следующим условиям:

• $|\; y\; |\; \ge \; 1\; \{\backslash \; displaystyle\; |\; y\; |\; \backslash \; geq\; 1\}$
• $|\; х\; у\; |\; \le \; п\; \{\backslash \; displaystyle\; |\; ху\; |\; \backslash \; leq\; p\}$
• $(\forall \; n\; \ge \; 0)\; (xynz\; \in \; L)\; \{\backslash \; displaystyle\; (\backslash \; forall\; n\; \backslash \; geq\; 0)\; (xy\; ^\; \{n\}\; z\; \backslash \; in\; L)\}$

$y\; \{\backslash \; displaystyle\; y\}$- это подстрока, которую можно перекачивать (удалять или повторять любое количество раз, и результирующая строка всегда находится в $L\; \{\backslash \; displaystyle\; L\}$). (1) означает, что цикл $y\; \{\backslash \; displaystyle\; y\}$, который нужно прокачивать, должен иметь длину не менее единицы; (2) означает, что цикл должен выполняться в пределах первых символов $p\; \{\backslash \; displaystyle\; p\}$. $|\; х\; |\; \{\backslash \; displaystyle\; |\; x\; |\}$должен быть меньше, чем $p\; \{\backslash \; displaystyle\; p\}$(заключение (1) и (2)), но кроме этого, есть не является ограничением для $x\; \{\backslash \; displaystyle\; x\}$и $z\; \{\backslash \; displaystyle\; z\}$.

Простыми словами, для любого обычного языка $L\; \{\backslash \; displaystyle\; L\}$, любое достаточно длинное слово $w\; \{\backslash \; displaystyle\; w\}$(в $L\; \{\backslash \; displaystyle\; L\}$) можно разделить на 3 части. т.е. $w\; =\; xyz\; \{\backslash \; displaystyle\; w\; =\; xyz\}$, так что все строки $xynz\; \{\backslash \; displaystyle\; xy\; ^\; \{n\}\; z\}$для $n\; \ge \; 0\; \{\backslash \; displaystyle\; n\; \backslash \; geq\; 0\}$также находятся в $L\; \{\backslash \; displaystyle\; L\}$.

Ниже приводится формальное выражение леммы о накачке.

$(\forall \; L\; \subseteq \; \Sigma \; \ast )\; (регулярный\; (L)\; \Rightarrow \; ((\exists \; p\; \ge \; 1)\; ((\forall \; w\; \in \; L)\; ((|\; w\; |\; \ge \; p)\; \Rightarrow \; ((\exists \; x,\; y,\; z\; \in \; \Sigma \; \ast )\; (вес\; знак\; равно\; xyz\; \wedge \; (|\; y\; |\; \ge \; 1\; \wedge \; |\; ху\; |\; \le \; p\; \wedge \; (\forall \; n\; \ge \; 0)\; (xynz\; \in \; L))))))))\; \{\backslash \; displaystyle\; \{\backslash \; begin\; \{array\}\; \{l\}\; (\; \backslash \; forall\; L\; \backslash \; substeq\; \backslash \; Sigma\; ^\; \{*\})\; \backslash \backslash \backslash \; quad\; (\{\backslash \; t\_dv\; \{regular\}\}\; (L)\; \backslash \; Rightarrow\; \backslash \backslash \backslash \; quad\; ((\backslash \; exists\; p\; \backslash \; geq\; 1)\; ((\backslash \; forall\; w\; \backslash \; in\; L)\; ((|\; w\; |\; \backslash \; geq\; p)\; \backslash \; Rightarrow\; \backslash \backslash \backslash \; quad\; ((\backslash \; exists\; x,\; y,\; z\; \backslash \; in\; \backslash \; Sigma\; ^\; \{*\})\; (w\; =\; xyz\; \backslash \; land\; (|\; y\; |\; \backslash \; geq\; 1\; \backslash \; land\; |\; xy\; |\; \backslash \; leq\; p\; \backslash \; land\; (\backslash \; forall\; n\; \backslash \; geq\; 0)\; (xy\; ^\; \{n\}\; z\; \backslash \; in\; L)))))))\; \backslash \; end\; \{array\}\}\}$

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

Например, язык $L\; =\; \{anbn:\; n\; \ge \; 0\}\; \{\backslash \; displaystyle\; L\; =\; \backslash \; \{a\; ^\; \{n\}\; b\; ^\; \{n\}:\; n\; \backslash \; geq\; 0\; \backslash \}\}$по алфавиту $\Sigma \; =\; \{a,\; b\}\; \{\backslash \; displaystyle\; \backslash \; Sigma\; =\; \backslash \; \{a,\; b\; \backslash \}\}$может быть показано как нерегулярное следующим образом:

Пусть $w,\; x,\; y,\; z,\; p\; \{\backslash \; displaystyle\; w,\; x,\; y,\; z,\; p\}$и $n\; \{\backslash \; displaystyle\; n\}$используется в формальном выражении для леммы о накачке выше. Мы предполагаем, что существует некоторая константа $p\; \{\backslash \; displaystyle\; p\}$. Пусть $w\; \{\backslash \; displaystyle\; w\}$в $L\; \{\backslash \; displaystyle\; L\}$задается как $w\; =\; apbp\; \{\backslash \; displaystyle\; w\; =\; a\; ^\; \{p\; \}\; b\; ^\; \{p\}\}$, которая является строкой длиннее, чем $p\; \{\backslash \; displaystyle\; p\}$. По лемме о накачке должно быть некоторое разложение $w\; =\; x\; y\; z\; \{\backslash \; displaystyle\; w\; =\; xyz\}$с $|\; х\; у\; |\; \le \; p\; \{\backslash \; displaystyle\; |\; xy\; |\; \backslash \; leq\; p\}$и $|\; y\; |\; \ge \; 1\; \{\backslash \; displaystyle\; |\; y\; |\; \backslash \; geq\; 1\}$такой, что $xyiz\; \{\backslash \; displaystyle\; xy\; ^\; \{i\}\; z\}$в $L\; \{\backslash \; displaystyle\; L\}$для каждого $i\; \ge \; 0\; \{\backslash \; displaystyle\; i\; \backslash \; geq\; 0\}$. Использование $|\; х\; у\; |\; \le \; p\; \{\backslash \; displaystyle\; |\; xy\; |\; \backslash \; leq\; p\}$, мы знаем, что $y\; \{\backslash \; displaystyle\; y\}$состоит только из экземпляров $a\; \{\backslash \; displaystyle\; a\}$. Более того, поскольку $|\; y\; |\; \ge \; 1\; \{\backslash \; displaystyle\; |\; y\; |\; \backslash \; geq\; 1\}$, он содержит по крайней мере один экземпляр буквы $a\; \{\backslash \; displaystyle\; a\}$. Теперь прокачиваем $y\; \{\backslash \; displaystyle\; y\}$вверх: $xy\; 2\; z\; \{\backslash \; displaystyle\; xy\; ^\; \{2\}\; z\}$имеет больше экземпляров буквы $a\; \{\backslash \; displaystyle\; a\}$, чем буква $b\; \{\backslash \; displaystyle\; b\}$, поскольку мы добавили несколько экземпляров $a\; \{\backslash \; displaystyle\; a\}$без добавления экземпляров $b\; \{\backslash \; displaystyle\; b\}$. Следовательно, $x\; y\; 2\; z\; \{\backslash \; displaystyle\; xy\; ^\; \{2\}\; z\}$не находится в $L\; \{\backslash \; displaystyle\; L\}$. Мы пришли к противоречию. Следовательно, предположение, что $L\; \{\backslash \; displaystyle\; L\}$является регулярным (т.е. существует такой $p\; \{\backslash \; displaystyle\; p\}$), должно быть неверным. Следовательно, $L\; \{\backslash \; displaystyle\; L\}$не является регулярным.

Доказательство того, что язык сбалансированных (т.е. правильно вложенных) скобок не является регулярным, следует той же идее. Для $p\; \{\backslash \; displaystyle\; p\}$существует строка сбалансированных круглых скобок, которая начинается с более чем $p\; \{\backslash \; displaystyle\; p\}$левых скобок, так что $y\; \{\backslash \; displaystyle\; y\}$будет состоять полностью из левых скобок. Повторяя $y\; \{\backslash \; displaystyle\; y\}$, мы можем создать строку, которая не содержит одинакового количества левых и правых круглых скобок, и поэтому их нельзя сбалансировать.

Идея доказательства: всякий раз, когда достаточно длинная строка xyz распознается конечным автоматом, он должен достичь некоторого состояния ($qs\; =\; qt\; \{\backslash \; displaystyle\; q\_\; \{s\}\; =\; q\_\; \{t\}\}$) дважды. Следовательно, после повторения ("прокачки") средней части $y\; \{\backslash \; displaystyle\; y\}$сколь угодно часто (xyyz, xyyyz,...) слово все равно будет распознаваться.

Для каждого На регулярном языке существует конечный автомат (FSA), который принимает этот язык. Подсчитывается количество состояний в таком FSA, и этот счет используется как длина накачки $p\; \{\backslash \; displaystyle\; p\}$. Для строки длиной не менее $p\; \{\backslash \; displaystyle\; p\}$пусть $q\; 0\; \{\backslash \; displaystyle\; q\_\; \{0\}\}$будет начальным состоянием и пусть $q\; 1,...,\; qp\; \{\backslash \; displaystyle\; q\_\; \{1\},...,\; q\_\; \{p\}\}$- последовательность следующих $p\; \{\backslash \; displaystyle\; p\}$состояний, посещенных как строка испускается. Поскольку FSA имеет только $p\; \{\backslash \; displaystyle\; p\}$состояний, в этой последовательности $p\; +\; 1\; \{\backslash \; displaystyle\; p\; +\; 1\}$посещенных состояний должны быть по крайней мере одно состояние, которое повторяется. Напишите $q\; s\; \{\backslash \; displaystyle\; q\_\; \{s\}\}$для такого состояния. Переходы, которые переводят машину от первой встречи состояния $qs\; \{\backslash \; displaystyle\; q\_\; \{s\}\}$ко второй встрече состояния $qs\; \{\backslash \; displaystyle\; q\_\; \{s\}\}$соответствует некоторой строке. Эта строка называется $y\; \{\backslash \; displaystyle\; y\}$в лемме, и поскольку машина будет соответствовать строке без части $y\; \{\backslash \; displaystyle\; y\}$, или если строка $y\; \{\backslash \; displaystyle\; y\}$повторяется любое количество раз, условия леммы удовлетворяются.

Например, на следующем изображении показан FSA.

FSA принимает строку: abcd . Так как эта строка имеет длину, по меньшей мере, равную количеству состояний, которое равно четырем, принцип ячейки указывает, что должно быть по крайней мере одно повторяющееся состояние среди начального состояния и следующих четырех посещенных состояний. В этом примере только $q\; 1\; \{\backslash \; displaystyle\; q\_\; \{1\}\}$является повторяющимся состоянием. Поскольку подстрока bc выполняет переходы, которые начинаются в состоянии $q\; 1\; \{\backslash \; displaystyle\; q\_\; \{1\}\}$и заканчиваются в состоянии $q\; 1\; \{\backslash \; displaystyle\; q\_\; \{1\}\}$, эта часть может быть повторена, и FSA все равно примет, выдав строку abcbcd . В качестве альтернативы, часть bc может быть удалена, и FSA все равно согласится предоставить строку ad . В терминах леммы о накачке строка abcd разбивается на $x\; \{\backslash \; displaystyle\; x\}$часть a, a $y\; \{\; \backslash \; displaystyle\; y\}$часть bc и $z\; \{\backslash \; displaystyle\; z\}$часть d.

Если язык $L\; \{\backslash \; displaystyle\; L\}$является регулярным, то существует число $p\; \ge \; 1\; \{\backslash \; displaystyle\; p\; \backslash \; geq\; 1\}$( длина накачки) так, чтобы каждая строка $uwv\; \{\backslash \; displaystyle\; uwv\}$в $L\; \{\backslash \; displaystyle\; L\}$с | w | ≥ p можно записать в виде

$uwv\; =\; uxyzv\; \{\backslash \; displaystyle\; uwv\; =\; uxyzv\}$

со строками $x\; \{\backslash \; displaystyle\; x\}$, $y\; \{\backslash \; displaystyle\; y\}$и $z\; \{\backslash \; displaystyle\; z\}$такие, что $|\; х\; у\; |\; \le \; п\; \{\backslash \; Displaystyle\; |\; ху\; |\; \backslash \; Leq\; р\}$, $|\; y\; |\; \ge \; 1\; \{\backslash \; displaystyle\; |\; y\; |\; \backslash \; geq\; 1\}$и

$uxyizv\; \{\backslash \; displaystyle\; uxy\; ^\; \{i\}\; zv\}$находится в $L\; \{\backslash \; displaystyle\; L\}$для каждого целого числа $i\; \ge \; 0\; \{\backslash \; displaystyle\; i\; \backslash \; geq\; 0\}$.

Отсюда для стандартной версии выше следует особый случай, с обоими $u\; \{\backslash \; displaystyle\; u\}$и $v\; \{\backslash \; displaystyle\; v\}$- пустая строка.

Поскольку общая версия предъявляет более строгие требования к языку, ее можно использовать для доказательства нерегулярности многих других языков, таких как $\{ambncn:\; m\; \ge \; 1\; и\; n\; \ge \; 1\}\; \{\backslash \; displaystyle\; \backslash \; \{a\; ^\; \{m\}\; b\; ^\; \{n\}\; c\; ^\; \{n\}:\; m\; \backslash \; geq\; 1\; \{\backslash \; text\; \{and\}\}\; n\; \backslash \; geq\; 1\; \backslash \}\}$.

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

Например, рассмотрим следующий язык:

$L\; =\; \{u\; v\; w\; x\; y:\; u,\; y\; \in \; \{0,\; 1,\; 2,\; 3\}\; \ast ;\; v,\; w,\; x\; \in \; \{0,\; 1,\; 2,\; 3\}\; \wedge \; (v\; =\; w\; \vee \; v\; =\; x\; \vee \; x\; =\; w)\}\; \cup \; \{w:\; w\; \in \; \{0,\; 1,\; 2,\; 3\}\; \ast \; \wedge \; ровно\; 1\; 7\; символов\; в\; w\; -\; тройки\}\; \{\backslash \; displaystyle\; \{\backslash \; begin\; \{matrix\}\; L\; =\; \backslash \; \{uvwxy:\; u,\; y\; \backslash \; in\; \backslash \; \{0,1,2,3\; \backslash \}\; ^\; \{*\};\; v,\; w,\; x\; \backslash \; in\; \backslash \; \{0,1,2,3\; \backslash \}\; \backslash \; land\; (v\; =\; w\; \backslash \; lor\; v\; =\; x\; \backslash \; lor\; x\; =\; w)\; \backslash \}\; \backslash \backslash \; \backslash \; cup\; \backslash \; \backslash \; \{w:\; w\; \backslash \; in\; \backslash \; \{0,1,\; 2,\; 3\; \backslash \}\; ^\; \{*\}\; \backslash \; land\; \{\backslash \; text\; \{точно\}\}\; \{\backslash \; tfrac\; \{1\}\; \{7\}\}\; \{\backslash \; text\; \{символов\; в\}\}\; w\; \{\backslash \; text\; \{это\; тройки\}\}\; \backslash \}\; \backslash \; end\; \{matrix\}\}\}$.

Другими словами, $L\; \{\backslash \; displaystyle\; L\}$содержит все строки в алфавите $\{0,\; 1,\; 2,\; 3\}\; \{\backslash \; displaystyle\; \backslash \; \{0,1,2,3\; \backslash \}\}$с подстрокой длиной 3, включающей повторяющийся символ, а также все строки в этом алфавите, где ровно 1/7 символов строки - тройки. Это нестандартный язык, но его все еще можно «накачать» с помощью $p\; =\; 5\; \{\backslash \; displaystyle\; p\; =\; 5\}$. Предположим, что некоторая строка s имеет длину не менее 5. Тогда, поскольку в алфавите всего четыре символа, по крайней мере два из первых пяти символов в строке должны быть дубликатами. Они разделены максимум тремя символами.

• Если повторяющиеся символы разделены 0 или 1 символами, перекачайте один из двух других символов в строке, что не повлияет на подстроку, содержащую дубликаты.
• Если повторяющиеся символы разделены 2 или 3 символа, прокачивайте 2 символа, разделяющих их. При перекачивании вниз или вверх создается подстрока размером 3, содержащая 2 повторяющихся символа.
• Второе условие $L\; \{\backslash \; displaystyle\; L\}$гарантирует, что $L\; \{\backslash \; displaystyle\; L\}$не является правильным: рассмотрим строку $(013)\; 3\; m\; (012)\; i\; \{\backslash \; displaystyle\; (013)\; ^\; \{3m\}\; (012)\; ^\; \{i\}\}$. Эта строка находится в $L\; \{\backslash \; displaystyle\; L\}$точно тогда, когда $i\; =\; 4\; m\; \{\backslash \; displaystyle\; i\; =\; 4m\}$и, следовательно, $L\; \{\backslash \; displaystyle\; L\}$не является регулярным по теореме Майхилла – Нероде.

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

• Лемма о накачке для контекстно-свободных языков
• Лемма Огдена

1. ^Рабин, Майкл ; Скотт, Дана (апрель 1959 г.). «Конечные автоматы и проблемы их решения» (PDF). Журнал исследований и разработок IBM. 3 (2): 114–125. doi : 10.1147 / ряд.32.0114. Архивировано 14 декабря 2010 г. CS1 maint: непригодный url (ссылка ) Здесь: Лемма 8, стр.119
2. ^Бар-Гилель, Ю. ; Perles, M.; Шамир, Э. (1961), «О формальных свойствах грамматик простой фразеологической структуры», Zeitschrift für Phonetik, Sprachwissenschaft und Kommunikationsforschung, 14 (2): 143–172
3. ^Джон Э. Хопкрофт; Раджив Мотвани; Джеффри Д. Ульман (2003). Введение в теорию автоматов, языки и вычисления. Эддисон Уэсли. Здесь: Раздел 4.6, с.166
4. ^Берстель, Жан; Лаув, Аарон; Ройтенауэр, Кристоф; Салиола, Франко В. (2009). Комбинаторика слов. Слова Кристоффеля и их повторы. Серия монографий CRM. 27 . Провиденс, Род-Айленд: Американское математическое общество. п. 86. ISBN 978-0-8218-4480-9. Zbl 1161.68043.
5. ^Савич, Уолтер (1982). Абстрактные машины и грамматики. п. 49. ISBN 978-0-316-77161-0.
6. ^Джон Э. Хопкрофт и Джеффри Д. Уллман (1979). Введение в теорию автоматов, языки и вычисления. Ридинг / МА: Эддисон-Уэсли. ISBN 978-0-201-02988-8.Здесь: стр. 72, упражнение 3.2 (которое дает несколько менее общую версию, требующую | w | = p) и 3.3

• Lawson, Mark V. (2004). Конечные автоматы. Чепмен и Холл / CRC. ISBN 978-1-58488-255-8. Zbl 1086.68074.
• Сипсер, Майкл (1997). «1.4: Нерегулярные языки». Введение в теорию вычислений. PWS Publishing. С. 77–83. ISBN 978-0-534-94728-6. Zbl 1169.68300.
• Хопкрофт, Джон Э. ; Уллман, Джеффри Д. (1979). Введение в теорию автоматов, языки и вычисления. Ридинг, Массачусетс: издательство Addison-Wesley Publishing. ISBN 978-0-201-02988-8. Zbl 0426.68001.(см. Главу 3.)
• Бахадыр Хусаинов; Анил Нероде (6 декабря 2012 г.). Теория автоматов и ее приложения. Springer Science Business Media. ISBN 978-1-4612-0171-7.