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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 2: Строка 2:
 
|about=О разрастании
 
|about=О разрастании
 
|statement=<tex>L</tex> - регулярный <tex>\Rightarrow</tex> <tex>\exists n \:\forall \omega : |\omega| \geqslant n, \omega \in L \: \exists x,y,z : \omega=xyz, y\neq \epsilon, |xy|\leqslant n, \forall k \geqslant 0\: xy^{k}z\in L</tex>
 
|statement=<tex>L</tex> - регулярный <tex>\Rightarrow</tex> <tex>\exists n \:\forall \omega : |\omega| \geqslant n, \omega \in L \: \exists x,y,z : \omega=xyz, y\neq \epsilon, |xy|\leqslant n, \forall k \geqslant 0\: xy^{k}z\in L</tex>
|proof=L - регулярный <tex>\Rightarrow</tex> <tex>\exists</tex> автомат <tex>A : \: n=|Q|</tex>
+
|proof=L - регулярный <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> подходит.
 
}}
 
}}
 +
 +
 +
Чаще используется отрицание леммы для доказательства нерегулярности языка.
 +
 +
 +
Пример 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>, что не является правильной скобочной последовательностью. Значит правильная скобочная последовательность не регулярный язык.
 +
 +
Пример 2.  Язык <tex>0^a1^a</tex>
 +
Для <tex>\forall n</tex> мы берём <tex>\omega=0^n1^n</tex>. Так как <tex>|xy|\leqslant n</tex>, то <tex>y=0^b</tex>. Берём <tex>k=2</tex> и получаем <tex>xy^kz=0^{n+b}1^n</tex>, что не является элементом нашего языка, значит наш язык не регулярен.

Версия 04:23, 5 октября 2010

Лемма (О разрастании):
[math]L[/math] - регулярный [math]\Rightarrow[/math] [math]\exists n \:\forall \omega : |\omega| \geqslant n, \omega \in L \: \exists x,y,z : \omega=xyz, y\neq \epsilon, |xy|\leqslant n, \forall k \geqslant 0\: xy^{k}z\in L[/math]
Доказательство:
[math]\triangleright[/math]
L - регулярный [math]\Rightarrow[/math] [math]\exists[/math] автомат [math]A : \: n=|Q|[/math] допускающий этот язык. Возьмём [math]\omega\in L : |\omega|\geqslant n[/math] тогда рассмотрим переходы в автомате [math]\langle s,\omega\rangle \vdash\langle u_1, \omega[0]^{-1}\omega\dots\vdash\langle u_{l},\epsilon\rangle, \: l\geqslant n[/math]. Так как [math]l\geqslant n[/math], то возьмём первое совпадение состояний в автомате [math]u_i, u_j[/math]. В нашем автомате для [math]\omega : \: \langle s, xyz\rangle \vdash^*\langle u_i, yz\rangle\vdash^*\langle u_j, z\rangle\vdash^*\langle u_l, \epsilon\rangle[/math]. Тогда [math]xy^kz[/math] подходит.
[math]\triangleleft[/math]


Чаще используется отрицание леммы для доказательства нерегулярности языка.


Пример 1. Правильная скобочная последовательность. Для [math]\forall n[/math] мы берём [math]\omega=(^n)^n[/math]. Так как [math]|xy|\leqslant n[/math], то [math]y=(^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], что не является элементом нашего языка, значит наш язык не регулярен.