Пусть дан какой-то <tex>n</tex> для него предъявляем слово <tex>\omega=0^n1^n</tex>. После этого слово <tex>\omega</tex> как-то разбили на <tex>x, y, z</tex>. Так как <tex>|xy|\leqslant n</tex>, то из-за выбранного слова <tex>y=0^b</tex>, где <tex>b</tex> больше нуля. Для любого такого разбиения берём <tex>k=2</tex> и получаем <tex>xy^kz=0^{n+b}1^n</tex>, что не является элементом множества слов языка <tex>\{0^a1^a\}_{a\geqslant 0}</tex>, значит этот язык не регулярен.
'''Интерпретация булевых формул с кванторами как игр для двух игроков'''
Рассмотрим формулу <tex>\exists x_1 \forall x_2 \exists x_3 \dots Q x_n = \Psi(x_1,\dots ,x_n)</tex>, где <tex>Q</tex> - квантор зависящий от чётности <tex>n</tex>. Теперь возьмём двух игроков и первый будет ставить <tex>x</tex> с нечётными номерами, а второй с чётными. Если в итоге получается истина, то побеждает первый игрок, если получается ложь, то выигрывает второй. Если <tex>\Psi</tex> истинна, то побеждает второй игрок, в противном случае побеждает первый (при правильных ходах). Пусть <tex>\Psi</tex> истинно, тогда отделим первый квантор. <tex>\exists x_1\Phi(x1)</tex>, тогда по предположению есть такой <tex>x_1</tex>, что <tex>\Phi(x_1)</tex> будет истинно. Верно и для любого с предположением для лжи. В итоге получаем, верное утверждение.
