Изменения
Нет описания правки
'''Пример 1. ''' Правильная скобочная последовательность.
Для <tex>\forall n</tex> мы берём <tex>\omega=(^n)^n</tex>. Так как <tex>|xy|\leqslant n</tex>, то <tex>y=(^b</tex>. Берём <tex>k=2</tex> и получаем <tex>xy^kz=(^{n+b})^n</tex>, что не является правильной скобочной последовательностью. Значит правильная скобочная последовательность не регулярный язык.
'''Пример 2. ''' Язык <tex>0^a1^a</tex>
Для <tex>\forall n</tex> мы берём <tex>\omega=0^n1^n</tex>. Так как <tex>|xy|\leqslant n</tex>, то <tex>y=0^b</tex>. Берём <tex>k=2</tex> и получаем <tex>xy^kz=0^{n+b}1^n</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> ложно, тогда
