Изменения

Пусть <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>.