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

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

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

Теоретический раздел
Часовой пояс: UTC + 4 часа [ Летнее время ]
MathHelpPlanet.com RSS-лента Математического форума

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


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

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


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


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


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


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


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


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


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

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


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

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

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

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


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




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


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


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


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


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


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

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


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


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


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


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


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


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


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


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


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



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


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


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


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


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


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

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


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


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


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

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


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


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

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


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


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


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

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