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

Лемма (О разрастании):

[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]