Изменения

{| id="toc" class="toc plainlinks" summary="Contents" style="clear:both;"! {{MediaWiki:Toc}}:| [[#lemma|Лемма]] '''·''' [[#Доказательства нерегулярности языков|Доказательства нерегулярности языков ]] '''·Лемма о разрастании''' [[#См. также|См(лемма о накачке, англ. также]] '''·'pumping lemma'') — лемма, позволяющая во многих случаях проверить, является ли данный язык [[#ПримечанияРегулярные языки: два определения и их эквивалентность|Примечаниярегулярным]] '''·'''.[[#Литература|Литература]]== Лемма о разрастании ==|}__NOTOC__

|id= ==lemma==|about=о разрастании<ref>Лемму также часто называют ''леммой , о накачке''</ref>

Пусть <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> для всех <tex> k \geqslant 0</tex>.

[[Файл:Consp_lemma.png||left|240px|]] Пусть <tex>L</tex> - — регулярный язык над алфавитом <tex>\Sigma</tex>.<br/>Пусть длина слов из языка ограничена, тогда полагая <tex>n = \max\limits_{l \in L}|l| + 1</tex>, получим пустое множество слов длины не менее <tex>n</tex>, откуда утверждение автоматически верно.[[Файл:Consp_lemma.png||left|240px|]]Пусть слова из языка могут иметь сколь угодно большую длину. Т. к. регулярный язык Поскольку [[Теорема Клини (совпадение классов автоматных и регулярных языков)|регулярный язык являетсяавтоматным]] автоматным тогда , то найдётся автомат <tex>A</tex>, допускающий язык <tex>L</tex>. Обозначим размер автомата Пусть <tex>An</tex>— размер автомата. Докажем, как что <tex>n</tex>удовлетворяет условию леммы. В языке <tex>L<br/tex> найдётся Возьмём произвольное слово <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},\epsilonvarepsilon\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 \geqslant 1</tex> такое что для любого слова <tex>uwv</tex> из языка <tex>L</tex>, где <tex>|w| \geqslant n</tex> может быть записано в форме <tex>uwv = uxyzv</tex>,где слова <tex>x</tex>, <tex>y</tex> и <tex>z</tex> такие, что <tex>|xy| \leqslant n</tex>, <tex>|y| \geqslant 1</tex> и <tex>uxy^izv</tex> принадлежит языку <tex>L</tex> для любого целого числа <tex>i \geqslant 0</tex>.|proof=Исходя из формулировки леммы в общем виде, стандартная версия леммы, которая описана выше, является особым случаем, в котором строки <tex>u</tex> и <tex>v</tex> пусты. Доказательство леммы в общем виде аналогично доказательству стандартной версии леммы, с тем отличием, что строки <tex>u</tex> и <tex>v</tex> теперь могут быть как не пусты, так и пусты.

}}'''Замечание.''' Поскольку лемма в общем виде накладывает более жесткие требования на язык, то она может быть использована для доказательства нерегулярности многих других языков, таких как <tex> L =\{ a^mb^nc^n : m \geqslant 1 , n \geqslant 1 \}</tex>. = Доказательства = Использование леммы для доказательства нерегулярности языков == Для доказательства нерегулярности языка можно использовать свойства регулярных и автоматных языков.<br/>Часто часто удобно использовать отрицание леммы о разрастании. Пусть <tex>L</tex> - — язык над алфавитом <tex>\Sigma</tex>. Если для любого натурального <tex>n</tex> найдётся такое слово <tex>\omega</tex> из данного языка, что его длина будет не меньше <tex> n</tex> и при любом разбиении на три слова <tex>x,y,z</tex> такие, что <tex>y</tex> непустое и длина <tex>xy</tex> не больше <tex>n</tex>, существует такое <tex>k</tex>, что <tex>xy^kz \notin L</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= \{a^{i}b^{j}c^{k} \mid i \ne 1, j \geqslant 0, k \geqslant 0\} \cup \{ ab^a1{i}c^a{i} \mid i \geqslant 1\}</tex> '''Докажем, что он нерегулярный.''' Для этого рассмотрим вспомогательный язык <tex>L'= \{ ab^{i}_c^{ai} \mid i \geqslant 01\}</tex> ===Пусть дан какой-то и докажем его нерегулярность. Воспользуемся предложенным в предыдущем пункте подходом. Для фиксированного <tex>n</tex> для него предъявляем выберем слово <tex>\omega=0ab^n1nc^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 \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>yi =0, j \geqslant 1, k \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 \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=2aab^jc^k</tex> и получаем . Выберем <tex>xyx = \varepsilon, y = aa, z = b^jc^kzk</tex>.# <tex> i \geqslant 3, j \geqslant 1, k \geqslant 1 </tex>. Слово имеет вид <tex>\omega=0aaaa^{n+i-3}b^jc^k</tex>. Выберем <tex> x = \varepsilon, y = a, z = aaa^{i-3}1b^jc^nk</tex>. '''Таким образом''', язык <tex> L </tex>удовлетворяет второй части леммы и при этом является нерегулярным, что доказывает тот факт, что лемма о разрастании '''не ''' является элементом множества слов достаточным для регулярности языка. ===Пример языка , удовлетворяющего лемме в общем виде===Рассмотрим другой пример.  <tex>L_1 = \{ uvwxy \mid u, y \in \{0,1 ,2,3 \}^a1* \wedge v,w,x \in \{ 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 \}^a* \wedge</tex> <tex>\dfrac{1}_{a7}</tex> из символов слова <tex>w</tex> является символом <tex>3 \geqslant 0}</tex> <tex>L = L_1 \cup L_2</tex> '''Докажем, что он нерегулярный.''' Предположим, что некоторая строка языка <tex>L</tex> имеет длину <tex>n=5</tex>. Поскольку в алфавите всего четыре символа, то как минимум два символа из пяти в этой строке будут одинаковыми, и они разделены максимум тремя символами::Если дубликаты разделены нулями или единицами, накачаем один из двух остальных символов в строке, которые не повлияют на подстроку, которая содержит дубликаты.:Если дубликаты разделены двойками или тройками, накачаем <tex>2</tex> символа, разделяющих их. Накачка также уменьшает или увеличивает результат во время создания подстроки размера <tex>3</tex>, значит этот язык которая содержит <tex>2</tex> продублированных символа.Второе условие языка <tex>L</tex> обеспечивает, что <tex>L</tex> — нерегулярный, то есть в нем бесконечное число строк, которые принадлежат <tex>L</tex>, но не регуляренмогут быть получены путям разрастания некоторой меньшей строки в <tex>L</tex>.

* [[Интерпретация булевых формул Булевые формулы с кванторами как игр игры для двух игроков]] == Примечания Источники информации ==<references* [http://en.wikipedia.org/>== Литература ==wiki/Pumping_lemma_for_regular_languages Wikipedia — Pumping lemma for regular languages]* ''Хопкрофт Д., Мотвани Р., Ульман Д.'' — '''Введение в теорию автоматов, языков и вычислений''', 2-е изд. : Пер. с англ. — Москва, М.:Издательский дом «Вильямс», 2002. — 528 сС. 144. : — ISBN 5-8459-0261-4 (рус.)