Изменения

Пусть <tex>L</tex> - регулярный язык над алфавитом <tex>\RightarrowSigma</tex>, тогда найдётся автомат <tex>A</tex> , допускающий язык <tex>\existsL</tex> автомат . Обозначим размер автомата <tex>A : \: </tex>, как <tex>n=|Q|</tex> допускающий этот язык. Возьмём В языке <tex>\omega\in L : |</tex> найдётся слово <tex>\omega|\geqslant </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\geqslant </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, \epsilonvarepsilon\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>.  "Картинка"

'''Доказательство нерегулярности языка''' Чаще используется отрицание леммы для доказательства нерегулярности языка. Пусть <tex>L</tex> - язык над алфавитом <tex>\Sigma</tex>. Если для любого натурального <tex>n</tex> найдётся такое слово <tex>\omega</tex> из данного языка, что его длина будет не меньше <tex> n</tex> и при любом разбиении на три слова <tex>x,y,z</tex> такие, что <tex> : y\neq \varepsilon</tex>, длина <tex>xy</tex> не больше <tex>n</tex>, есть <tex>k</tex> такое, что <tex>xy^kz \overline\in L</tex>, то язык <tex>L</tex> - не регулярный.

'''Пример 1''' Язык правильных скобочных последовательностей не регулярен. Правильная скобочная последовательность. Для Пусть дан какой-то <tex>\forall n</tex> мы берём для него предъявляем слово <tex>\omega=(^n)^n</tex>. После этого наше слово как-то разбили на <tex>x, y, z</tex>. Так как <tex>|xy|\leqslant n</tex>, то из-за выбранного слова <tex>y=(^b</tex>, где <tex>b</tex> больше нуля. Берём Для любого такого разбиения берём <tex>k=2</tex> и получаем <tex>xy^kz=(^{n+b})^n</tex>, что не является правильной скобочной последовательностью. Значит правильная скобочная последовательность язык правильных скобочных последовательностей не регулярный язык.