Изменения

'''Лемма о разрастании''' (лемма о накачке, англ. ''pumping lemma'') — лемма, позволяющая во многих случаях проверить, является ли данный язык [[КатегорияРегулярные языки: Теория формальных два определения и их эквивалентность|регулярным]].== Лемма о разрастании == {{Лемма|id= ==lemma==|about=о разрастании, о накачке|statement=Пусть <tex>L</tex> — [[Регулярные языки: два определения и их эквивалентность|регулярный язык]] над алфавитом <tex>\Sigma</tex>, тогда существует такое <tex>n</tex>, что для любого слова <tex> \omega \in L</tex> длины не меньше <tex>n</tex> найдутся слова <tex> x,y,z \in \Sigma^*</tex>, для которых верно: <tex>xyz=\omega, y\neq \varepsilon, |xy|\leqslant n</tex> и <tex>\forall k \geqslant 0~xy^{k}z\in L</tex>.|proof=[[Файл: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| \leqslant n</tex>.}}'''Замечание.''' Условие леммы не является достаточным для регулярности языка. ''(См. [[#Пример нерегулярного языка, для которого выполняется лемма о разрастании|пример]])'' == Лемма о разрастании в общем виде ==

|id= ==lemma==|about=О о разрастании, о накачке в общем виде

Пусть Если язык <tex>L</tex> - регулярный язык над алфавитом является регулярным, то существует число <tex>n \Sigmageqslant 1</tex>, тогда существует такое что для любого слова <tex>nuwv</tex>, такой что для любого слова из языка <tex> \omega \in L</tex>, длины не меньше где <tex> |w| \geqslant n </tex> найдутся может быть записано в форме <tex>uwv = uxyzv</tex>,где слова <tex> x</tex>,<tex>y,</tex> и <tex>z \in \Sigma^*</tex>такие, для которых верно что <tex>xyz=\omega, y\neq \varepsilon, |xy|\leqslant n</tex>, <tex>|y| \geqslant 1</tex> и <tex>xyuxy^{k}z\in izv</tex> принадлежит языку <tex>L</tex> для всех любого целого числа <tex> k i \geqslant 0</tex>.

Пусть <tex>L</tex> - регулярный язык над алфавитом <tex>\Sigma</tex>, тогда найдётся автомат <tex>A</tex>, допускающий язык <tex>L</tex>. Обозначим размер автомата <tex>A</tex>, как <tex>n</tex>. В языке <tex>L</tex> найдётся слово <tex>\omega</tex> длины не меньше <tex>n</tex>. Рассмотрим переходы Исходя из формулировки леммы в автомате <tex>\langle sобщем виде,\omega\rangle \vdash\langle u_1стандартная версия леммы, \omega[0]^{-1}\omega\rangle\vdash\dots\vdash\langle u_{l}которая описана выше,\epsilon\rangleявляется особым случаем, \: l\geqslant n</tex>. Так как <tex>l</tex> не меньше количества состояний в автомате котором строки <tex>n</tex>, то в переходах будет совпадение. Пусть <tex>u_iu</tex> и <tex>u_jv</tex> - первое совпадениепусты. Тогда Доказательство леммы в нашем слове <tex>\omega</tex> можно размножить кусокобщем виде аналогично доказательству стандартной версии леммы, который отвечает за переходс тем отличием, от состояния что строки <tex>u_iu</tex> к состоянию и <tex>u_jv</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>так и пусты.

'''Доказательство нерегулярности Рассмотрим такой подход на примере языка'''правильных скобочных последовательностей. Для фиксированного <tex>n</tex> предъявляем слово <tex>\omega=(^n)^n</tex>. Пусть <tex>\omega</tex> как-то разбили на <tex>x, y, z</tex>. Так как <tex>|xy|\leqslant n</tex>, то <tex>y=(^b</tex>, где <tex>b > 0</tex>. Для любого такого разбиения берём <tex>k=2</tex> и получаем <tex>xy^kz=(^{n+b})^n</tex>, что не является правильной скобочной последовательностью. Значит, язык правильных скобочных последовательностей нерегулярен.

Чаще используется отрицание леммы == Пример нерегулярного языка, для доказательства нерегулярности которого выполняется лемма о разрастании=====Пример языка. Пусть , удовлетворяющего стандартной версии леммы===Рассмотрим следующий язык: <tex>L</tex> - язык над алфавитом <tex>= \{ a^{i}b^{j}c^{k} \Sigma</tex>. Если для любого натурального <tex>n</tex> найдётся такое слово <tex>mid i \omega</tex> из данного языкаne 1, что его длина будет не меньше <tex> n</tex> и при любом разбиении на три слова <tex>x,yj \geqslant 0,z</tex> такие, что <tex> : y</tex> не пустое слово, длина <tex>xy</tex> не больше <tex>n</tex>, есть <tex>k</tex> такое, что <tex>xy\geqslant 0\} \cup \{ ab^{i}c^kz {i} \mid i \overlinegeqslant 1\in L</tex>, то язык <tex>L}</tex> - не регулярный.

'''Пример 1''' Язык правильных скобочных последовательностей не регулярен. Пусть дан какой-то Предположим, что язык <tex>nL </tex> для него предъявляем слово регулярный. Заметим, что <tex>L' = L \cap \omega=({ab^n){*}c^n{*}\} </tex>. После этого слово <tex>\omega</tex> как-то разбили на <tex>x В силу того, yчто пересечение регулярных языков регулярно, z</tex>имеем в правой части равенства регулярный язык. Так как <tex>|xy|\leqslant n</tex>При этом в левой части стоит язык, то из-за выбранного слова <tex>y=(^b</tex>нерегулярность которого была доказана ранее. Значит наше предположение неверно, где <tex>b</tex> больше нуля. Для любого такого разбиения берём <tex>k=2</tex> и получаем язык <tex>xy^kz=(^{n+b})^nL </tex>, что не является правильной скобочной последовательностью. Значит язык правильных скобочных последовательностей не регулярный языкнерегулярный.

'''Пример 2Докажем, что язык удовлетворяет лемме о разрастании.''' Выберем в лемме <tex> n = 2 </tex>. Язык Это означает, что длина рассматриваемых слов не меньше <tex> 2 </tex> (иными словами <tex> i + j + k \geqslant 2 \,</tex>). Для каждого случая значений <tex> i, j, k </tex> выберем соответствующие слова <tex> x, y </tex> и <tex>z </tex> из леммы. Легко проверить, что в каждом из приведенных ниже случаев условие леммы выполняется: # <tex> i = 0, j = 0, k \geqslant 2 </tex>. Слово имеет вид <tex>\omega=c^k</tex>. Выберем <tex> x = \varepsilon, y = c, z = c^{k-1}</tex>.# <tex> i = 0, j \geqslant 1, k \geqslant 0 </tex>. Слово имеет вид <tex>\omega=b^a1jc^ak</tex>. Выберем <tex> x = \varepsilon, y = b, z = b^{j-1}_{c^k</tex>.# <tex> i = 1, j \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 \geqslant 1, k \geqslant 1 </tex>. Слово имеет вид <tex>\omega=aab^jc^k</tex>. Выберем <tex> x = \varepsilon, y = aa, z = b^jc^k</tex>.# <tex> i \geqslant 03, j \geqslant 1, k \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>nL </tex> удовлетворяет второй части леммы и при этом является нерегулярным, что доказывает тот факт, что лемма о разрастании '''не''' является достаточным для него предъявляем слово регулярности языка. ===Пример языка, удовлетворяющего лемме в общем виде===Рассмотрим другой пример.  <tex>L_1 = \{ uvwxy \mid u, y \in \{ 0,1 ,2,3 \}^* \wedge v,w,x \omegain \{ 0,1,2,3 \} \wedge ( v = w \vee v =x \vee x =w) \}</tex> <tex>L_2 = \{ w \mid w \in \{ 0,1 ,2,3 \}^n1^n* \wedge</tex> <tex>\dfrac{1}{7}</tex> из символов слова <tex>w</tex>. После этого слово является символом <tex>3 \omega} </tex> как-то разбили на  <tex>L = L_1 \cup L_2</tex>x '''Докажем, yчто он нерегулярный.''' Предположим, zчто некоторая строка языка <tex>L</tex>. Так как имеет длину <tex>|xy|\leqslant n=5</tex>. Поскольку в алфавите всего четыре символа, то как минимум два символа из-за выбранного слова пяти в этой строке будут одинаковыми, и они разделены максимум тремя символами::Если дубликаты разделены нулями или единицами, накачаем один из двух остальных символов в строке, которые не повлияют на подстроку, которая содержит дубликаты.:Если дубликаты разделены двойками или тройками, накачаем <tex>y=0^b2</tex>символа, где разделяющих их. Накачка также уменьшает или увеличивает результат во время создания подстроки размера <tex>b3</tex> больше нуля. Для любого такого разбиения берём , которая содержит <tex>k=2</tex> и получаем продублированных символа.Второе условие языка <tex>xy^kz=0^{n+b}1^nL</tex>обеспечивает, что <tex>L</tex> — нерегулярный, то есть в нем бесконечное число строк, которые принадлежат <tex>L</tex>, но не является элементом множества слов языка могут быть получены путям разрастания некоторой меньшей строки в <tex>\{0^a1^a\}_{a\geqslant 0}L</tex>. == См. также ==* [[Лемма о разрастании для КС-грамматик]]* [[Булевые формулы с кванторами как игры для двух игроков]] == Источники информации ==* [http://en.wikipedia.org/wiki/Pumping_lemma_for_regular_languages Wikipedia — Pumping lemma for regular languages]* Хопкрофт Д., Мотвани Р., Ульман Д. — Введение в теорию автоматов, языков и вычислений, 2-е изд. : Пер. с англ. — М.:Издательский дом «Вильямс», значит этот язык не регулярен2002. — С. 144.— ISBN 5-8459-0261-4 [[Категория: Теория формальных языков]][[Категория: Автоматы и регулярные языки]][[Категория: Свойства конечных автоматов]]