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

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

Пусть [math]L[/math] - регулярный язык над алфавитом [math]\Sigma[/math], тогда существует [math]n[/math], такой что для любого слова [math] \omega \in L[/math], длины не меньше [math] n [/math] найдутся слова [math] x,y,z \in \Sigma^*[/math], для которых верно [math]xyz=\omega, y\neq \varepsilon, |xy|\leqslant n[/math] и [math]xy^{k}z\in L[/math] для всех [math] k \geqslant 0[/math].

Доказательство:

[math]\triangleright[/math]

[math]L[/math] - регулярный [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], что не является элементом нашего языка, значит наш язык не регулярен.

Интерпретация булевых формул с кванторами как игр для двух игроков

Рассмотрим формулу [math]\exists x_1 \forall x_2 \exists x_3 \dots Q x_n = \Psi(x_1,\dots ,x_n)[/math], где [math]Q[/math] - квантор зависящий от чётности [math]n[/math]. Теперь возьмём двух игроков и первый будет ставить [math]x[/math] с нечётными номерами, а второй с чётными. Если в итоге получается истина, то побеждает первый игрок, если получается ложь, то выигрывает второй. Если [math]\Psi[/math] истинна, то побеждает второй игрок, в противном случае побеждает первый (при правильных ходах). Пусть [math]\Psi[/math] истинно, тогда отделим первый квантор. [math]\exists x_1\Phi(x1)[/math], тогда по предположению есть такой [math]x_1[/math], что [math]\Phi(x_1)[/math] будет истинно. Верно и для любого с предположением для лжи. В итоге получаем, верное утверждение.