Изменения
→Пример доказательства без использования леммы
Рассмотрим язык праильных скобочных последовательностей. Для фиксированного <tex>n</tex> предъявляем слово <tex>\omega=(^n)^n</tex>. Пусть <tex>\omega</tex> как-то разбили на <tex>x, y, z</tex>. Так как <tex>|xy|\leqslant n</tex>, то <tex>y=(^b</tex>, где <tex>b > 0</tex>. Для любого такого разбиения берём <tex>k=2</tex> и получаем <tex>xy^kz=(^{n+b})^n</tex>, что не является правильной скобочной последовательностью. Значит, язык правильных скобочных последовательностей нерегулярен.
=== Пример доказательства без использования леммы ===
Докажем нерегулярность языка <tex>0^a 1^b 2^b, a \geqslant 1, b \geqslant 0</tex>. Заметим, что здесь условие леммы о накачке выполнено <tex>(n = 1, x = \varepsilon, y = a0)</tex>. Докажем нерегулярность языка с помощью свойств ДКА. Пусть для языка существует автомат <tex>A</tex> c <tex>k</tex> состояниями. Пусть после <tex>a</tex> нулей на вход поступило <tex>k</tex> единиц. При помощи рассуждений, аналогичных приведенным в доказательстве леммы, получаем, что с момента завершения считывания нулей до последнего считывания единицы автомат посетит <tex>k + 1</tex> состояние, т. е. хотя бы в одном из них он окажется дважды. Пусть при первом посещении этого состояния автомат считал <tex>i</tex> единиц, при втором — <tex>j</tex>. Поскольку <tex>0^a 1^i 2^i</tex> принимается автоматом, а <tex>0^a 1^j 2^i</tex> — не принимается, то при подаче автомату, находящемуся в этом состоянии, <tex>i</tex> двоек, автомат, с одной стороны, должен оказаться в допускающем состоянии, с другой — в недопускающем.
== См. также ==
* [[Лемма о разрастании для КС-грамматик]]
