'''Лемма о разрастании'''<ref>Лемму также часто называют ''леммой о накачке''.</ref>(Pumping lemma) — лемма, позволяющая во многих случаях проверить, является ли данный язык [[Регулярные языки: два определения и их эквивалентность|регулярным]].
== Лемма о разрастании ==
__TOC__
{{Лемма
Наконец, поскольку <tex>u_i</tex> и <tex>u_j</tex> — первое совпадение, среди состояний <tex>s, u_1, \ldots, u_i, \ldots, u_{j-1}</tex> нет повторяющихся. Значит, выполняется требование <tex>|xy| \le n</tex>.
}}
'''Замечание.''' Условие леммы не является достаточным для регулярности языка. ''(См. [[#Пример доказательства без использования леммынерегулярного языка, для которого выполняется лемма о разрастании|пример 2]])''
== Доказательства Использование леммы для доказательства нерегулярности языков ==Для доказательства нерегулярности языка можно использовать свойства регулярных и автоматных языков.
Часто Для доказательства нерегулярности языка часто удобно использовать отрицание леммы о разрастании. Пусть <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>0n</tex> предъявляем слово <tex>\omega=(^a 1n)^b 2^bn</tex>. Пусть <tex>\omega</tex> как-то разбили на <tex>x, a \geqslant 1y, b \geqslant 0z</tex>. Заметим, что здесь условие леммы о накачке выполнено Так как <tex>(|xy|\leqslant n = 1</tex>, x то <tex>y= \varepsilon(^b</tex>, y = где <tex>b > 0)</tex>. {{TODO|t=предыдущее утверждение — неправда, возьмем Для любого такого разбиения берём <tex>k=02</tex>, получим и получаем <tex>1xy^b2kz=(^{n+b})^n</tex> , что не в языке}}является правильной скобочной последовательностью. Значит, язык правильных скобочных последовательностей нерегулярен. == Пример нерегулярного языка, для которого выполняется лемма о разрастании==
Докажем нерегулярность языка с помощью свойств ДКА. Пусть для языка существует автомат <tex>A</tex> c <tex>k</tex> состояниями. Пусть после <tex>a</tex> нулей на вход поступило <tex>k</tex> единиц. При помощи рассуждений, аналогичных приведенным в доказательстве леммы, получаем, что с момента завершения считывания нулей до последнего считывания единицы автомат посетит <tex>k + 1</tex> состояние, т. е. хотя бы в одном из них он окажется дважды. Пусть при первом посещении этого состояния автомат считал <tex>i</tex> единиц, при втором — <tex>j</tex>. Поскольку <tex>0^a 1^i 2^i</tex> принимается автоматом, а <tex>0^a 1^j 2^i</tex> — не принимается, то при подаче автомату, находящемуся в этом состоянии, <tex>i</tex> двоек, автомат, с одной стороны, должен оказаться в допускающем состоянии, с другой — в недопускающем.
== См. также ==
