Изменения

{| id="toc" class="toc plainlinks" summary="Contents" style="clear:both;"! {{MediaWiki:Toc}}:| [[Категория: Теория формальных #lemma|Лемма]] '''·''' [[#Доказательства нерегулярности языков|Доказательства нерегулярности языков]] '''·''' [[#См. также|См. также]] '''·''' [[#Литература|Литература]]|}__NOTOC__

Пусть <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>xy^{k}z\in L</tex> для всех <tex> k \geqslant 0</tex>.

Пусть <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>A</tex>, как <tex>n</tex>. В языке <tex>L</tex> найдётся слово <tex>\omega</tex> длины не меньше <tex>n</tex>. Рассмотрим переходы в автомате <tex>\langle s,\omega\rangle \vdash\langle u_1, \omega[0]^{-1}\omega\rangle\vdash\dots\vdash\langle u_{l},\epsilon\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>.  [[Файл:Regularpicture.jpg]]  То есть если верно <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 \overline\in L</tex>, то язык <tex>L</tex> - не регулярный.  '''Пример 1''' Язык === Нерегулярность языка правильных скобочных последовательностей не регулярен. ===

 '''Пример 2''' Язык === Нерегулярность языка <tex>\{0^a1^a\}_{a\geqslant 0}</tex>===