Доказательство нерегулярности языков: лемма о разрастании — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 5: Строка 5:
 
Пусть <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>, тогда существует <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>.
 
|proof=
 
|proof=
<tex>L</tex> - регулярный <tex>\Rightarrow</tex> <tex>\exists</tex> автомат <tex>A : \: n=|Q|</tex> допускающий этот язык. Возьмём <tex>\omega\in L : |\omega|\geqslant n</tex> тогда рассмотрим переходы в автомате <tex>\langle s,\omega\rangle \vdash\langle u_1, \omega[0]^{-1}\omega\dots\vdash\langle u_{l},\epsilon\rangle, \: l\geqslant n</tex>. Так как <tex>l\geqslant n</tex>, то возьмём первое совпадение состояний в автомате <tex>u_i, u_j</tex>. В нашем автомате для <tex>\omega : \: \langle s, xyz\rangle \vdash^*\langle u_i, yz\rangle\vdash^*\langle u_j, z\rangle\vdash^*\langle u_l, \epsilon\rangle</tex>. Тогда <tex>xy^kz</tex> подходит.  
+
Пусть <tex>L</tex> - регулярный язык над алфавитом <tex>\Sigma</tex>, тогда найдётся автомат <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>. То есть если верно <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>.  
 +
 
 +
"Картинка"
 
}}
 
}}
  
  
Чаще используется отрицание леммы для доказательства нерегулярности языка.
+
'''Доказательство нерегулярности языка'''
 +
 
 +
Чаще используется отрицание леммы для доказательства нерегулярности языка. Пусть <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'''  Правильная скобочная последовательность.
+
'''Пример 1''' Язык правильных скобочных последовательностей не регулярен.
Для <tex>\forall n</tex> мы берём <tex>\omega=(^n)^n</tex>. Так как <tex>|xy|\leqslant n</tex>, то <tex>y=(^b</tex>. Берём <tex>k=2</tex> и получаем <tex>xy^kz=(^{n+b})^n</tex>, что не является правильной скобочной последовательностью. Значит правильная скобочная последовательность не регулярный язык.
+
   
 +
Пусть дан какой-то <tex>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>, что не является правильной скобочной последовательностью. Значит язык правильных скобочных последовательностей не регулярный язык.
  
 
'''Пример 2'''  Язык <tex>0^a1^a</tex>
 
'''Пример 2'''  Язык <tex>0^a1^a</tex>

Версия 03:51, 8 октября 2010

Лемма (О разрастании):
Пусть [math]L[/math] - регулярный язык над алфавитом [math]\Sigma[/math], тогда существует [math]n[/math], такой что для любого слова [math] \omega \in L[/math], длины не меньше [math] n [/math] найдутся слова [math] x,y,z \in \Sigma^*[/math], для которых верно [math]xyz=\omega, y\neq \varepsilon, |xy|\leqslant n[/math] и [math]xy^{k}z\in L[/math] для всех [math] k \geqslant 0[/math].
Доказательство:
[math]\triangleright[/math]

Пусть [math]L[/math] - регулярный язык над алфавитом [math]\Sigma[/math], тогда найдётся автомат [math]A[/math], допускающий язык [math]L[/math]. Обозначим размер автомата [math]A[/math], как [math]n[/math]. В языке [math]L[/math] найдётся слово [math]\omega[/math] длины не меньше [math]n[/math]. Рассмотрим переходы в автомате [math]\langle s,\omega\rangle \vdash\langle u_1, \omega[0]^{-1}\omega\rangle\vdash\dots\vdash\langle u_{l},\epsilon\rangle, \: l\geqslant n[/math]. Так как [math]l[/math] не меньше количества состояний в автомате [math]n[/math], то в переходах будет совпадение. Пусть [math]u_i[/math] и [math]u_j[/math] - первое совпадение. Тогда в нашем слове [math]\omega[/math] можно размножить кусок, который отвечает за переход, от состояния [math]u_i[/math] к состоянию [math]u_j[/math]. То есть если верно [math]\langle s, xyz\rangle \vdash^*\langle u_i, yz\rangle\vdash^*\langle u_j, z\rangle\vdash^*\langle u_l, \varepsilon\rangle[/math], то тогда верно [math]\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[/math]. Тогда автомат [math]A[/math] допускает слово [math]xy^kz[/math], следовательно [math]xy^kz[/math] принадлежит регулярному языку [math]L[/math].

"Картинка"
[math]\triangleleft[/math]


Доказательство нерегулярности языка

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


Пример 1 Язык правильных скобочных последовательностей не регулярен.

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

Пример 2 Язык [math]0^a1^a[/math] Для [math]\forall n[/math] мы берём [math]\omega=0^n1^n[/math]. Так как [math]|xy|\leqslant n[/math], то [math]y=0^b[/math]. Берём [math]k=2[/math] и получаем [math]xy^kz=0^{n+b}1^n[/math], что не является элементом нашего языка, значит наш язык не регулярен.


Интерпретация булевых формул с кванторами как игр для двух игроков

Рассмотрим формулу [math]\exists x_1 \forall x_2 \exists x_3 \dots Q x_n = \Psi(x_1,\dots ,x_n)[/math], где [math]Q[/math] - квантор зависящий от чётности [math]n[/math]. Теперь возьмём двух игроков и первый будет ставить [math]x[/math] с нечётными номерами, а второй с чётными. Если в итоге получается истина, то побеждает первый игрок, если получается ложь, то выигрывает второй. Если [math]\Psi[/math] истинна, то побеждает второй игрок, в противном случае побеждает первый (при правильных ходах). Пусть [math]\Psi[/math] истинно, тогда отделим первый квантор. [math]\exists x_1\Phi(x1)[/math], тогда по предположению есть такой [math]x_1[/math], что [math]\Phi(x_1)[/math] будет истинно. Верно и для любого с предположением для лжи. В итоге получаем, верное утверждение.