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

В теории формальных языков большое значение имеют утверждения, в которых формулируется необходимое условие принадлежности языка к тому или иному классу языков. Эти утверждения известны в литературе под названием лемм о разрастании (или лемм о "накачке"). С помощью этих лемм удается доказать, что тот или иной язык не является языком данного класса, например, не является регулярным, контекстно-свободным и т.п. Доказывать подобного рода "отрицательные" утверждения гораздо труднее, чем "положительные" (что язык есть язык данного класса [cbm]C[/cbm] ), ибо в последнем случае требуется придумать любую грамматику соответствующего класса, порождающую данный язык, а в первом нужно каким-то образом доказать, что не существует грамматики этого класса, порождающей язык. Применение лемм о разрастании состоит в следующем: доказав, что предлагаемый язык не удовлетворяет условию леммы о разрастании, мы можем быть уверены в том, что он заведомо не принадлежит соответствующему классу языков, и нам нечего и пытаться искать для него грамматику того же класса.

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

Начнем с леммы о разрастании для регулярных языков. Эта лемма (см. теорему 7.10) утверждает, что любой регулярный язык допускает представление всех своих достаточно длинных цепочек в виде соединения трех цепочек, причем средняя цепочка из этих трех не пуста, ограничена по длине, и ее "накачка" — повторение любое число раз — или выбрасывание не выводит за пределы языка (т.е. дает цепочки, принадлежащие данному регулярному языку).

Теорема 7.10. Если [cbm]L[/cbm] — регулярный язык, то существует натуральная константа [cbm]k_L[/cbm] (зависящая от [cbm]L[/cbm] ), такая, что для любой цепочки [cbm]x\in L[/cbm] , длина которой не меньше [cbm]k_L[/cbm] , [cbm]x[/cbm] допускает представление в виде [cbm]x=uvw[/cbm] , где [cbm]v\ne\lambda[/cbm] и [cbm]|v|\leqslant k_L[/cbm] , причем для любого [cbm]n\geqslant0[/cbm] цепочка [cbm]x_n=uv^nw\in L[/cbm] .

Поскольку язык [cbm]L[/cbm] регулярен, то, согласно теореме Клини (см. теорему 7.6), существует конечный автомат [cbm]M=(V,Q,q_0,F,\delta)[/cbm] допускающий его, т.е. [cbm]L=L(M)[/cbm] (в силу теоремы 7.7 о детерминизации можно считать [cbm]M[/cbm] детерминированным автоматом). Положив [cbm]k_L=|Q|[/cbm] , т.е. введя константу [cbm]k_L[/cbm] как число состояний конечного автомата [cbm]M[/cbm] , фиксируем произвольно цепочку [cbm]x\in L[/cbm] , длина [cbm]l[/cbm] которой не меньше [cbm]k_L[/cbm] . Так как [cbm]l>0[/cbm] , то цепочка [cbm]x[/cbm] не является пустой, и мы можем положить [cbm]x=x(1)\ldots x(l),~l>0[/cbm] .

Поскольку конечный автомат [cbm]M[/cbm] является детерминированным, то существует единственный путь, ведущий из начального состояния [cbm]q_0[/cbm] в одно из заключительных состояний [cbm]q_f[/cbm] , на котором читается [cbm]x[/cbm] (рис. 7.28).

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

Так как длина [cbm]l[/cbm] цепочки [cbm]x[/cbm] не меньше числа состояний [cbm]M[/cbm] , т.е. числа всех вершин графа [cbm]M[/cbm] , то, поскольку число вершин в любом пути ровно на единицу больше числа дуг в этом пути (т.е. длины пути), число вершин в рассмотренном выше пути будет больше, чем число всех вершин графа. Это значит, что хотя бы одна из вершин данного пути повторяется и она, таким образом, в силу следствия 5.1, содержится в некотором контуре. Обозначим эту вершину через [cbm]p[/cbm] . Тогда путь, несущий цепочку [cbm]x[/cbm] , разбивается на три части (рис. 7.29):

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

1) путь из [cbm]q_0[/cbm] в [cbm]p[/cbm] ;

2) контур, проходящий через [cbm]p[/cbm] ;

3) путь из [cbm]p[/cbm] в [cbm]q_f[/cbm] .

Обозначая через [cbm]u[/cbm] цепочку, читаемую на первой части пути, через [cbm]{v}[/cbm] — цепочку, читаемую на контуре, а через [cbm]w[/cbm] — цепочку, читаемую на третьей части, получим [cbm]x=uvw[/cbm] , причем поскольку любой контур есть простой путь, то [cbm]|v|\leqslant k_L[/cbm] (длина простого пути не может быть больше, чем число вершин графа) и [cbm]v\ne\lambda[/cbm] , так как контур имеет ненулевую длину. Но теперь совершенно очевидно, что контур (на котором лежит вершина [cbm]p[/cbm] ) можно пройти (по пути из [cbm]q_0[/cbm] в [cbm]q_f[/cbm] ) любое число [cbm]n[/cbm] (при [cbm]n>0[/cbm] ) раз или ни разу. В первом случае на этом пути будет прочитана цепочка [cbm]u^nvw[/cbm] при [cbm]n>0[/cbm] , а во втором — и цепочка [cbm]uw[/cbm] . Таким образом, любая цепочка [cbm]x_n=uv^nw~(n\geqslant0)[/cbm] содержится в языке [cbm]L[/cbm] .


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

Рассмотрим теперь некоторые примеры доказательств нерегулярности языка с использованием леммы о разрастании. Стандартный ход рассуждений при решении таких задач состоит в предположении регулярности данного языка и последующем анализе возможности представить любую достаточно длинную цепочку языка в виде, указанном в условии леммы о разрастании. Анализируя все возможные случаи размещения "накачиваемой" подцепочки [cbm]{v}[/cbm] , мы должны получить противоречие.

Пример 7.12. а. Докажем нерегулярность языка [cbm]L_1=\{a^nb^n\colon\, n\geqslant0\}[/cbm] .

Выбирая [cbm]n[/cbm] настолько большим, чтобы оно превосходило [cbm]k_L[/cbm] (константу леммы), получаем следующие возможные случаи размещения средней подцепочки [cbm]{v}[/cbm] в цепочке [cbm]a^nb^n[/cbm] .

1. [cbm]v=a^s,~s<n[/cbm] , т.е. "накачиваемая" подцепочка целиком располагается в "зоне символов [cbm]a[/cbm] " (рис. 7.30,а).

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

Ясно, что накачка в этом случае выведет за пределы языка, так как при повторении цепочки [cbm]{v}[/cbm] число символов [cbm]a[/cbm] будет неограниченно расти, а число символов [cbm]b[/cbm] будет оставаться прежним.

2. [cbm]v=b^s,~s<n[/cbm] , т.е. "накачиваемая" подцепочка целиком располагается в "зоне символов [cbm]b[/cbm] " (рис. 7.30,б).

Накачка невозможна по той же причине, что и в предыдущем случае.

3. [cbm]v=a^pb^q[/cbm] , где [cbm]0<p<n,~0<q<n[/cbm] , т.е. "накачиваемая" подцепочка находится "на стыке зон символов [cbm]a[/cbm] и [cbm]b[/cbm] " (рис. 7.30,в).

В этом случае при накачке возникнет вхождение подцепочки [cbm]ba[/cbm] в слово, которое, следовательно, уже не принадлежит языку [cbm]L_1[/cbm] . Таким образом, рассматриваемый язык нерегулярен.

б. Докажем, что язык [cbm]L_2=L_1^{\ast}[/cbm] , где [cbm]L_1=\{a^nb^n\colon\, n\geqslant0\}[/cbm] , нерегулярный.

Полагая, что язык [cbm]L_2[/cbm] регулярен, возьмем слово [cbm](a^nb^n)^m[/cbm] для достаточно большого [cbm]n\,(m\geqslant1)[/cbm] .

Применяя такую же схему рассуждений, как и выше, легко убеждаемся в том, что цепочка [cbm]{v}[/cbm] не может состоять из одних символов [cbm]a[/cbm] или из одних символов [cbm]b[/cbm] .

Пусть [cbm]v=a^rb^s[/cbm] , где [cbm]r+s<n[/cbm] . Тогда, повторив цепочку [cbm]{v}[/cbm] два раза, получим слово [cbm]\ldots a^{n-r}a^rb^sa^rb^sb^{n-s}\ldots[/cbm] . Если [cbm]r\ne s[/cbm] , то цепочка такого вида не может принадлежать языку [cbm]L_2[/cbm] , так как в любом слове этого языка за подцепочкой символов [cbm]a[/cbm] следует подцепочка символов [cbm]b[/cbm] такой же длины. Но даже если [cbm]r=s[/cbm] , то получим подцепочку [cbm]a^nb^s[/cbm] , где [cbm]s<n[/cbm] (или [cbm]a^rb^n,~r<n[/cbm] ), что также противоречит определению языка [cbm]L_2[/cbm] . Аналогично рассматривается случай [cbm]v=b^ra^s~(r+s<n)[/cbm] (рис. 7.31).

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


Заметим, что в силу ограничения по длине на цепочку [cbm]{v}[/cbm] никакие способы ее размещения в указанной цепочке языка [cbm]L_2[/cbm] , кроме описанных выше, не возможны.

Полезно иметь в виду следствие из леммы о разрастании.

Следствие 7.4. Если [cbm]L[/cbm] — бесконечный регулярный язык, то в нем найдется последовательность слов, длины которых образуют возрастающую арифметическую прогрессию.

В качестве такой последовательности можно взять последовательность слов [cbm]x_n[/cbm] из формулировки леммы о разрастании. Их длины образуют арифметическую прогрессию со знаменателем [cbm]|v|[/cbm] (длина "накачиваемой" средней подцепочки).

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

1) [cbm]\{a^{n^2}\colon\,n\geqslant0\}[/cbm] — язык в однобуквенном алфавите, длины слов которого являются полными квадратами;
2) { [cbm]a^p\colon\,p[/cbm] — простое число}.

Можно доказать, что любой конечный язык регулярен и, более того, допускается конечным автоматом без контуров. Значит, последовательность цепочек, указанная в формулировке леммы, в таком случае не существует, но утверждение леммы остается истинным. Нужно всегда помнить простое логическое правило: утверждение вида "если А, то Б" равносильно утверждению вида "не А или Б".

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

Пример 7.13. Докажем нерегулярность языка правильных скобочных структур, порождаемых КС-грамматикой

[cbm]\bigl\langle\{(,)\}, \{S\}, S, \{S\to ()\mid (S)\mid SS\}\bigr\rangle[/cbm]

(см. грамматику [cbm]G_3[/cbm] в примере 7.5). Для доказательства поступим так: рассмотрим пересечение данного языка с регулярным языком [cbm]({}^{\ast})^{\ast}[/cbm] , который содержит все цепочки вида [cbm]({}^m)^n[/cbm] для любых натуральных [cbm]m,n\geqslant0[/cbm] . Поскольку каждая правильная скобочная структура содержит одинаковое число символов w(" и ")", то указанное пересечение будет языком [cbm]\{({}^n)^n\colon\,n\geqslant0\}[/cbm] . Если обозначить через [cbm]a[/cbm] nоткрывающую скобку" (символ "("), а через [cbm]b[/cbm] "закрывающую скобку" (символ ")"), то получим язык [cbm]L_1[/cbm] , который, как только что доказано, не является регулярным. Следовательно, предполагая регулярность языка правильных скобочных структур, мы вынуждены будем допустить и регулярность языка [cbm]L_1[/cbm] , так как пересечение регулярных языков в силу следствия 7.3 регулярно. Полученное противоречие и доказывает нерегулярность исходного языка. Заметим, что доказательство этого факта с использованием одной лишь леммы о разрастании было бы весьма затруднительно.

Замечание 7.12. С использованием "техники пересечения" можно доказать нерегулярность языка [cbm]L_2[/cbm] из примера 7.12 следующим образом. Так как язык

[cbm]L_1=L_2\cap a^{\ast}b^{\ast}=\{a^nb^n\colon\,n\geqslant0\}[/cbm]

нерегулярный, то и язык [cbm]L_2[/cbm] тоже не является регулярным.

Итак, можно вывести такой "рецепт": если возникают существенные затруднения в доказательстве нерегулярности какого-либо языка с помощью только леммы о разрастании, то можно попытаться пересечь этот язык с некоторым регулярным языком так, чтобы нерегулярность пересечения легко доказывалась с использованием леммы о разрастании.

Источник

Поделитесь с другими:

Если материал понравился Вам и оказался для Вас полезным, поделитесь им со своими друзьями!

Читать по теме:

Интересные статьи: