Изменения

|statement=Пусть <tex>L</tex> - регулярный язык над алфавитом <tex>\RightarrowSigma</tex> , тогда существует <tex>\exists n \:\forall \omega : |\omega| \geqslant n</tex>, такой что для любого слова <tex> \omega \in L \: \exists </tex>, длины не меньше <tex> n </tex> найдутся слова <tex> x,y,z : \in \Sigma^*</tex>, для которых верно <tex>xyz=\omega=xyz, y\neq \epsilonvarepsilon, |xy|\leqslant n, \forall k \geqslant 0\: </tex> и <tex>xy^{k}z\in L</tex>для всех <tex> k \geqslant 0</tex>.|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> подходит.