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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «{{Лемма |about=О разрастании |statement=<tex>L</tex> - регулярный <tex>\Rightarrow</tex> <tex>\exists n \:\forall \omega : |\omega| \geqsl…»)
 
Строка 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=
+
|proof=L - регулярный <tex>\Rightarrow</tex> <tex>\exists</tex> автомат <tex>A : \: n=|Q|</tex>
 
}}
 
}}

Версия 03:39, 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]\triangleleft[/math]
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Доказательство_нерегулярности_языков:_лемма_о_разрастании&oldid=3094»