Дискуссионный математический форумМатематический форум
Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 3 часа [ Летнее время ]
новый онлайн-сервис
число, сумма и дата прописью

Часовой пояс: UTC + 3 часа [ Летнее время ]


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

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


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


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


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


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


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


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


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

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


Путь автомата, несущий цепочку

1) путь из q_0 в p;

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

3) путь из p в q_f.


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




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


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


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


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


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


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

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


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


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


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


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


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


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


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


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


2. Доказательство нерегулярности языка



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


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


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


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


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


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

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


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


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


\bigl\langle\{(,)\}, \{S\}, S, \{S\to ()\mid (S)\mid SS\}\bigr\rangle

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


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


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

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


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

Математический форум (помощь с решением задач, обсуждение вопросов по математике).
Кнопка "Поделиться"
Если заметили ошибку, опечатку или есть предложения, напишите в комментариях.

Часовой пояс: UTC + 3 часа [ Летнее время ]


Яндекс.Метрика

Copyright © 2010-2023 MathHelpPlanet.com. All rights reserved