Изменения

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

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

[[Файл: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>.

'''Замечание.''' Условие леммы не является достаточным для регулярности языка. ''(См. [[#Нерегулярность языкаПример доказательства без использования леммы|пример2]])''

<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^a 1^b 2^b, a \geqslant 1, b \geqslant 0</tex> ===. Заметим, что здесь условие леммы о накачке выполнено <tex>(n = 1, x = \varepsilon, y = a)</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> двоек, автомат, с одной стороны, должен оказаться в допускающем состоянии, с другой — в недопускающем.