Изменения

Пусть <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>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>\{0^a1a 1^b 2^b, a\}_{ageqslant 1, b \geqslant 0}</tex> ===Пусть дан какой-то Заметим, что здесь условие леммы о накачке выполнено <tex>(n= 1, x = \varepsilon, y = a)</tex> . Докажем нерегулярность языка с помощью свойств ДКА. Пусть для него предъявляем слово языка существует автомат <tex>A</tex> c <tex>\omega=0^n1^nk</tex>состояниями. После этого слово Пусть после <tex>\omegaa</tex> как-то разбили нулей на вход поступило <tex>x, y, zk</tex>единиц. Так как При помощи рассуждений, аналогичных приведенным в доказательстве леммы, получаем, что с момента завершения считывания нулей до последнего считывания единицы автомат посетит <tex>|xy|\leqslant nk + 1</tex>состояние, то т. е. хотя бы в одном из-за выбранного слова них он окажется дважды. Пусть при первом посещении этого состояния автомат считал <tex>y=0^bi</tex>единиц, где при втором — <tex>bj</tex> больше нуля. Для любого такого разбиения берём Поскольку <tex>k=0^a 1^i 2^i</tex> и получаем принимается автоматом, а <tex>xy^kz=0^{n+b}a 1^nj 2^i</tex>— не принимается, то при подаче автомату, находящемуся в этом состоянии, что не является элементом множества слов языка <tex>\{0^a1^a\}_{a\geqslant 0}i</tex>двоек, автомат, с одной стороны, значит этот язык не регулярендолжен оказаться в допускающем состоянии, с другой — в недопускающем.