Лемма о разрастании для регулярных языков
В теории формальных языков большое значение имеют утверждения, в которых формулируется необходимое условие принадлежности языка к тому или иному классу языков. Эти утверждения известны в литературе под названием лемм о разрастании (или лемм о "накачке"). С помощью этих лемм удается доказать, что тот или иной язык не является языком данного класса, например, не является регулярным, контекстно-свободным и т.п. Доказывать подобного рода "отрицательные" утверждения гораздо труднее, чем "положительные" (что язык есть язык данного класса ), ибо в последнем случае требуется придумать любую грамматику соответствующего класса, порождающую данный язык, а в первом нужно каким-то образом доказать, что не существует грамматики этого класса, порождающей язык. Применение лемм о разрастании состоит в следующем: доказав, что предлагаемый язык не удовлетворяет условию леммы о разрастании, мы можем быть уверены в том, что он заведомо не принадлежит соответствующему классу языков, и нам нечего и пытаться искать для него грамматику того же класса.
Мы рассмотрим подобного рода утверждения для классов регулярных, контекстно-свободных и линейных языков.
Начнем с леммы о разрастании для регулярных языков. Эта лемма (см. теорему 7.10) утверждает, что любой регулярный язык допускает представление всех своих достаточно длинных цепочек в виде соединения трех цепочек, причем средняя цепочка из этих трех не пуста, ограничена по длине, и ее "накачка" — повторение любое число раз — или выбрасывание не выводит за пределы языка (т.е. дает цепочки, принадлежащие данному регулярному языку).
Теорема 7.10. Если — регулярный язык, то существует натуральная константа (зависящая от ), такая, что для любой цепочки , длина которой не меньше , допускает представление в виде , где и , причем для любого цепочка .
Поскольку язык регулярен, то, согласно теореме Клини (см. теорему 7.6), существует конечный автомат допускающий его, т.е. (в силу теоремы 7.7 о детерминизации можно считать детерминированным автоматом). Положив , т.е. введя константу как число состояний конечного автомата , фиксируем произвольно цепочку , длина которой не меньше . Так как , то цепочка не является пустой, и мы можем положить .
Поскольку конечный автомат является детерминированным, то существует единственный путь, ведущий из начального состояния в одно из заключительных состояний , на котором читается (рис. 7.28).
Так как длина цепочки не меньше числа состояний , т.е. числа всех вершин графа , то, поскольку число вершин в любом пути ровно на единицу больше числа дуг в этом пути (т.е. длины пути), число вершин в рассмотренном выше пути будет больше, чем число всех вершин графа. Это значит, что хотя бы одна из вершин данного пути повторяется и она, таким образом, в силу следствия 5.1, содержится в некотором контуре. Обозначим эту вершину через . Тогда путь, несущий цепочку , разбивается на три части (рис. 7.29):
1) путь из в ; 2) контур, проходящий через ; 3) путь из в .
Обозначая через цепочку, читаемую на первой части пути, через — цепочку, читаемую на контуре, а через — цепочку, читаемую на третьей части, получим , причем поскольку любой контур есть простой путь, то (длина простого пути не может быть больше, чем число вершин графа) и , так как контур имеет ненулевую длину. Но теперь совершенно очевидно, что контур (на котором лежит вершина ) можно пройти (по пути из в ) любое число (при ) раз или ни разу. В первом случае на этом пути будет прочитана цепочка при , а во втором — и цепочка . Таким образом, любая цепочка содержится в языке .
Примеры доказательств нерегулярности языка
Рассмотрим теперь некоторые примеры доказательств нерегулярности языка с использованием леммы о разрастании. Стандартный ход рассуждений при решении таких задач состоит в предположении регулярности данного языка и последующем анализе возможности представить любую достаточно длинную цепочку языка в виде, указанном в условии леммы о разрастании. Анализируя все возможные случаи размещения "накачиваемой" подцепочки , мы должны получить противоречие.
Пример 7.12. а. Докажем нерегулярность языка .
Выбирая настолько большим, чтобы оно превосходило (константу леммы), получаем следующие возможные случаи размещения средней подцепочки в цепочке .
1. , т.е. "накачиваемая" подцепочка целиком располагается в "зоне символов " (рис. 7.30,а).
Ясно, что накачка в этом случае выведет за пределы языка, так как при повторении цепочки число символов будет неограниченно расти, а число символов будет оставаться прежним.
2. , т.е. "накачиваемая" подцепочка целиком располагается в "зоне символов " (рис. 7.30,б).
Накачка невозможна по той же причине, что и в предыдущем случае.
3. , где , т.е. "накачиваемая" подцепочка находится "на стыке зон символов и " (рис. 7.30,в).
В этом случае при накачке возникнет вхождение подцепочки в слово, которое, следовательно, уже не принадлежит языку . Таким образом, рассматриваемый язык нерегулярен.
б. Докажем, что язык , где , нерегулярный.
Полагая, что язык регулярен, возьмем слово для достаточно большого .
Применяя такую же схему рассуждений, как и выше, легко убеждаемся в том, что цепочка не может состоять из одних символов или из одних символов .
Пусть , где . Тогда, повторив цепочку два раза, получим слово . Если , то цепочка такого вида не может принадлежать языку , так как в любом слове этого языка за подцепочкой символов следует подцепочка символов такой же длины. Но даже если , то получим подцепочку , где (или ), что также противоречит определению языка . Аналогично рассматривается случай (рис. 7.31).
Заметим, что в силу ограничения по длине на цепочку никакие способы ее размещения в указанной цепочке языка , кроме описанных выше, не возможны.
Полезно иметь в виду следствие из леммы о разрастании.
Следствие 7.4. Если — бесконечный регулярный язык, то в нем найдется последовательность слов, длины которых образуют возрастающую арифметическую прогрессию.
В качестве такой последовательности можно взять последовательность слов из формулировки леммы о разрастании. Их длины образуют арифметическую прогрессию со знаменателем (длина "накачиваемой" средней подцепочки).
Отсюда легко получается вывод о том, что не являются регулярными следующие языки:
1)  — язык в однобуквенном алфавите, длины слов которого являются полными квадратами; 2) {  — простое число}.
Можно доказать, что любой конечный язык регулярен и, более того, допускается конечным автоматом без контуров. Значит, последовательность цепочек, указанная в формулировке леммы, в таком случае не существует, но утверждение леммы остается истинным. Нужно всегда помнить простое логическое правило: утверждение вида "если А, то Б" равносильно утверждению вида "не А или Б".
В заключение обсудим еще одну схему доказательства нерегулярности языка с использованием как леммы о разрастании, так и алгебраических свойств класса регулярных языков, которые были установлены ранее.
Пример 7.13. Докажем нерегулярность языка правильных скобочных структур, порождаемых КС-грамматикой
(см. грамматику в примере 7.5). Для доказательства поступим так: рассмотрим пересечение данного языка с регулярным языком , который содержит все цепочки вида для любых натуральных . Поскольку каждая правильная скобочная структура содержит одинаковое число символов w(" и ")", то указанное пересечение будет языком . Если обозначить через nоткрывающую скобку" (символ "("), а через "закрывающую скобку" (символ ")"), то получим язык , который, как только что доказано, не является регулярным. Следовательно, предполагая регулярность языка правильных скобочных структур, мы вынуждены будем допустить и регулярность языка , так как пересечение регулярных языков в силу следствия 7.3 регулярно. Полученное противоречие и доказывает нерегулярность исходного языка. Заметим, что доказательство этого факта с использованием одной лишь леммы о разрастании было бы весьма затруднительно.
Замечание 7.12. С использованием "техники пересечения" можно доказать нерегулярность языка из примера 7.12 следующим образом. Так как язык
нерегулярный, то и язык тоже не является регулярным.
Итак, можно вывести такой "рецепт": если возникают существенные затруднения в доказательстве нерегулярности какого-либо языка с помощью только леммы о разрастании, то можно попытаться пересечь этот язык с некоторым регулярным языком так, чтобы нерегулярность пересечения легко доказывалась с использованием леммы о разрастании.
Если заметили ошибку, опечатку или есть предложения, напишите в комментариях.
|