177
правок
Изменения
Нет описания правки
[[Файл:Consp_lemma.png||left|240px|]] Пусть <tex>L</tex> — регулярный язык над алфавитом <tex>\Sigma</tex>. Поскольку [[Теорема Клини (совпадение классов автоматных и регулярных языков)|регулярный язык является автоматным]], то найдётся автомат <tex>A</tex>, допускающий язык <tex>L</tex>. Пусть <tex>n</tex> — размер автомата. Докажем, что <tex>n</tex> удовлетворяет условию леммы.
<br/>Возьмём произвольное слово <tex>\omega</tex> длины не меньше <tex>n</tex> из языка <tex>L</tex>. Рассмотрим переходы в автомате <tex>\langle s,\omega\rangle \vdash\langle u_1, \omega[0]^{-1}\omega\rangle\vdash\dots\vdash\langle u_{l},\varepsilon\rangle, \: l\geqslant n</tex>. Так как <tex>l</tex> не меньше количества состояний в автомате <tex>n</tex>, то в переходах будет совпадение. Пусть <tex>u_i</tex> и <tex>u_j</tex> — первое совпадение. Тогда, повторяя участок слова <tex>\omega</tex>, который отвечает за переход от <tex>u_i</tex> к <tex>u_j</tex>, получаем слово, допускаемое автоматом. То есть, если верно <tex>\langle s, xyz\rangle \vdash^*\langle u_i, yz\rangle\vdash^*\langle u_j, z\rangle\vdash^*\langle u_l, \varepsilon\rangle</tex>, то тогда верно <tex>\langle s, xy^kz\rangle \vdash^*\langle u_i, y^kz\rangle\vdash^*\langle u_j, y^{k-1}z\rangle\vdash^*\langle u_j, z\rangle\vdash^*\langle u_l, \varepsilon\rangle</tex>. Тогда автомат <tex>A</tex> допускает слово <tex>xy^kz</tex>, следовательно <tex>xy^kz</tex> принадлежит регулярному языку <tex>L</tex>.<br />
Наконец, поскольку <tex>u_i</tex> и <tex>u_j</tex> — первое совпадение, среди состояний <tex>s, u_1, \ldots, u_i, \ldots, u_{j-1}</tex> нет повторяющихся. Значит, выполняется требование <tex>|xy| \le leqslant n</tex>.
}}
'''Замечание.''' Условие леммы не является достаточным для регулярности языка. ''(См. [[#Пример нерегулярного языка, для которого выполняется лемма о разрастании|пример]])''
== Лемма о разрастании в общем виде ==
Если язык <tex>L</tex> является регулярным, то существует число <tex>p \ge geqslant 1</tex> такое что для любого слова <tex>uwv</tex> из языка <tex>L</tex>, где <tex>|w| \ge geqslant p</tex> может быть записано в форме <tex>uwv = uxyzv</tex>,где слова <tex>x</tex>, <tex>y</tex> и <tex>z</tex> такие, что <tex>|xy| \le leqslant p</tex>, <tex>|y| \ge geqslant 1</tex> и <tex>uxy^izv</tex> принадлежит языку <tex>L</tex> для любого целого числа <tex>i \ge geqslant 0</tex>.
Исходя из этого, стандартная версия леммы, которая описана выше, является особым случаем, в котором строки <tex>u</tex> и <tex>v</tex> пусты.
Поскольку лемма в общем виде накладывает более жесткие требования на язык, то она может быть использована для доказательства нерегулярности многих других языков, таких как <tex> L =\{ a^mb^nc^n : m \ge geqslant 1 , n \ge geqslant 1 \}</tex>.
== Использование леммы для доказательства нерегулярности языков ==
== Пример нерегулярного языка, для которого выполняется лемма о разрастании==
Рассмотрим следующий язык: <tex>L= \{ a^{i}b^{j}c^{k} \mid i \ne 1, j \ge geqslant 0, k \ge geqslant 0\} \cup \{ ab^{i}c^{i} \mid i \ge geqslant 1\}</tex>
'''Докажем, что он нерегулярный.''' Для этого рассмотрим вспомогательный язык <tex>L'= \{ ab^{i}c^{i} \mid i \ge 1\}</tex> и докажем его нерегулярность. Воспользуемся предложенным в предыдущем пункте подходом. Для фиксированного <tex>n</tex> выберем слово <tex>\omega=ab^nc^n</tex>. Заметим, что при любом разбиении <tex>\omega</tex> на <tex>x, y, z</tex> слово <tex> y </tex> не пусто (по условию леммы) и содержит только символы <tex> a </tex> и <tex> b </tex> (согласно выбранному слову и условию из леммы <tex>|xy|\leqslant n</tex>). Это означает, что при <tex> k = 0 </tex> слово <tex>xy^kz</tex> либо не содержит символа <tex> a </tex>, либо количество символов <tex> b</tex> меньше <tex> n </tex>. В обоих случаях полученное слово не принадлежит языку. Значит язык <tex> L' </tex> нерегулярный.
Предположим, что язык <tex> L </tex> регулярный. Заметим, что <tex>L' = L \cap \{ab^{*}c^{*}\} </tex>. В силу того, что пересечение регулярных языков регулярно, имеем в правой части равенства регулярный язык. При этом в левой части стоит язык, нерегулярность которого была доказана ранее. Значит наше предположение неверно, и язык <tex> L </tex> нерегулярный.
'''Докажем, что язык удовлетворяет лемме о разрастании.''' Выберем в лемме <tex> n = 2 </tex>. Это означает, что длина рассматриваемых слов не меньше <tex> 2 </tex> (иными словами <tex> i + j + k \ge geqslant 2 </tex>). Для каждого случая значений <tex> i, j, k </tex> выберем соответствующие слова <tex> x, y </tex> и <tex> z </tex> из леммы. Легко проверить, что в каждом из приведенных ниже случаев условие леммы выполняется: # <tex> i = 0, j = 0, k \ge geqslant 2 </tex>. Слово имеет вид <tex>\omega=c^k</tex>. Выберем <tex> x = \varepsilon, y = c, z = c^{k-1}</tex>.# <tex> i = 0, j \ge geqslant 1, k \ge geqslant 0 </tex>. Слово имеет вид <tex>\omega=b^jc^k</tex>. Выберем <tex> x = \varepsilon, y = b, z = b^{j-1}c^k</tex>.# <tex> i = 1, j \ge geqslant 1, j = k </tex>. Слово имеет вид <tex>\omega=ab^jc^j</tex>. Выберем <tex> x = \varepsilon, y = a, z = b^jc^j</tex>.# <tex> i = 2, j \ge geqslant 1, k \ge geqslant 1 </tex>. Слово имеет вид <tex>\omega=aab^jc^k</tex>. Выберем <tex> x = \varepsilon, y = aa, z = b^jc^k</tex>.# <tex> i \ge geqslant 3, j \ge geqslant 1, k \ge geqslant 1 </tex>. Слово имеет вид <tex>\omega=aaaa^{i-3}b^jc^k</tex>. Выберем <tex> x = \varepsilon, y = a, z = aaa^{i-3}b^jc^k</tex>.
'''Таким образом''', язык <tex> L </tex> удовлетворяет второй части леммы и при этом является нерегулярным, что доказывает тот факт, что лемма о разрастании '''не''' является достаточным для регулярности языка.
