Изменения

'''Лемма о разрастании''' (лемма о накачке, англ. ''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=О о разрастании, о накачке в общем виде|statement=Если язык <tex>L</tex> - регулярный является регулярным, то существует число <tex>n \Rightarrowgeqslant 1</tex> такое что для любого слова <tex>uwv</tex> из языка <tex>L</tex>, где <tex>\exists n \:\forall \omega : |\omegaw| \geqslant n</tex> может быть записано в форме <tex>uwv = uxyzv</tex>, \omega \in L \: \exists где слова <tex>x,y,z : \omega=xyz, y\neq \epsilon, |xy|\leqslant n, \forall k \geqslant 0\: xy^{k}z\in L</tex>|proof=L - регулярный , <tex>\Rightarrowy</tex> и <tex>\existsz</tex> автомат такие, что <tex>A : |xy| \: leqslant n=|Q|</tex> допускающий этот язык. Возьмём , <tex>\omega\in L : |\omegay|\geqslant n1</tex> тогда рассмотрим переходы в автомате и <tex>\langle s,\omega\rangle \vdash\langle u_1, \omega[0]uxy^{-1}\omega\dots\vdash\langle u_{l},\epsilon\rangle, \: l\geqslant nizv</tex> принадлежит языку <tex>L</tex>. Так как для любого целого числа <tex>li \geqslant n0</tex>.|proof=Исходя из формулировки леммы в общем виде, стандартная версия леммы, которая описана выше, является особым случаем, то возьмём первое совпадение состояний в автомате котором строки <tex>u_i, u_ju</tex>. В нашем автомате для и <tex>v</tex>\omega : \: \langle s, xyz\rangle \vdash^*\langle u_iпусты. Доказательство леммы в общем виде аналогично доказательству стандартной версии леммы, yz\rangle\vdash^*\langle u_jс тем отличием, z\rangle\vdash^*\langle u_l, \epsilon\rangleчто строки <tex>u</tex>. Тогда и <tex>xy^kzv</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>, что не является правильной скобочной последовательностью. Значит, язык правильных скобочных последовательностей нерегулярен.

'''Пример 1Докажем, что он нерегулярный.''' Для этого рассмотрим вспомогательный язык Правильная скобочная последовательность<tex>L'= \{ ab^{i}c^{i} \mid i \geqslant 1\}</tex> и докажем его нерегулярность. Воспользуемся предложенным в предыдущем пункте подходом. Для фиксированного <tex>\forall n</tex> мы берём выберем слово <tex>\omega=(ab^n)nc^n</tex>. Так как Заметим, что при любом разбиении <tex>|xy|\leqslant nomega</tex>на <tex>x, y, то z</tex> слово <tex>y=</tex> не пусто (^по условию леммы) и содержит только символы <tex> a </tex> и <tex> b</tex>(согласно выбранному слову и условию из леммы <tex>|xy|\leqslant n</tex>). Берём Это означает, что при <tex>k=20 </tex> и получаем слово <tex>xy^kz=(^{n+</tex> либо не содержит символа <tex> a </tex>, либо количество символов <tex> b})^</tex> меньше <tex> n</tex>, что . В обоих случаях полученное слово не является правильной скобочной последовательностьюпринадлежит языку. Значит правильная скобочная последовательность не регулярный язык<tex> L' </tex> нерегулярный.

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

'''Интерпретация булевых формул с кванторами как игр для двух игроковТаким образом''', язык <tex> L </tex> удовлетворяет второй части леммы и при этом является нерегулярным, что доказывает тот факт, что лемма о разрастании '''не'''является достаточным для регулярности языка.

===Пример языка, удовлетворяющего лемме в общем виде===Рассмотрим формулу другой пример.  <tex>L_1 = \{ uvwxy \exists x_1 mid u, y \forall x_2 in \exists x_3 { 0,1 ,2,3 \dots Q x_n = }^* \Psi(x_1wedge v,w,x \dots in \{ 0,1,2,x_n3 \} \wedge ( v = w \vee v = x \vee x =w)\}</tex> <tex>L_2 = \{ w \mid w \in \{ 0, где 1 ,2,3 \}^* \wedge</tex> <tex>\dfrac{1}{7}</tex> из символов слова <tex>Qw</tex> - квантор зависящий от чётности является символом <tex>3 \} </tex> <tex>nL = L_1 \cup L_2</tex> '''Докажем, что он нерегулярный. Теперь возьмём двух игроков и первый будет ставить ''' Предположим, что некоторая строка языка <tex>L</tex> имеет длину <tex>xn=5</tex> с нечётными номерами, а второй с чётными. Если Поскольку в итоге получается истинаалфавите всего четыре символа, то побеждает первый игроккак минимум два символа из пяти в этой строке будут одинаковыми, если получается ложьи они разделены максимум тремя символами::Если дубликаты разделены нулями или единицами, то выигрывает второйнакачаем один из двух остальных символов в строке, которые не повлияют на подстроку, которая содержит дубликаты. :Если дубликаты разделены двойками или тройками, накачаем <tex>\Psi2</tex> истиннасимвола, то побеждает второй игрокразделяющих их. Накачка также уменьшает или увеличивает результат во время создания подстроки размера <tex>3</tex>, в противном случае побеждает первый (при правильных ходах)которая содержит <tex>2</tex> продублированных символа. Пусть Второе условие языка <tex>\PsiL</tex> истиннообеспечивает, тогда отделим первый квантор. что <tex>\exists x_1\Phi(x1)L</tex>— нерегулярный, тогда по предположению то есть такой в нем бесконечное число строк, которые принадлежат <tex>x_1L</tex>, что но не могут быть получены путям разрастания некоторой меньшей строки в <tex>\Phi(x_1)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 [[Категория: Теория формальных языков]][[Категория: Автоматы и регулярные языки]][[Категория: Свойства конечных автоматов]]