== Упрощение доказательства нерегулярности примера ==
В данном примере мы хотели доказать, что выполнение леммы о накачке не свидетельствует о томПредположим, что язык - регулярный, для этого был приведён пример нерегулярного языка, для которого лемма выполнена. Однако доказательство нерегулярности довольно трудноеа , я предлагаю более простой вариантзначит, который будет яснее. Предположим, что язык - регулярный, тогда для него существует ДКА(пусть в нём $n$ состояний). Подадим на него $n+1 строку $ слово вида $ab^i $, где $i $ принадлежит от $1 $ до $n+1, согласно $. Согласно принципу Дирихле , хотя бы 2 слова должны попасть в одно и то же состояние. Пусть ; пусть это слова $ab^k$, $ab^l$, тогда если мы подадим подать на автомат слова $ab^k ckc^k $ и $ab^l clc^k$, то они также попадут в одно состояние. Заметим, однако что $ab^k ckc^k $ принадлежит языку, а $ab^l clc^k $ {{-- -}} не принадлежит (. Получается противоречие) => , ведь оба слова перейдут в одно и то же состояние, но так как $ab^kc^k$ переходит в терминальное состояние, то и $ab^lc^k$ тоже переходит в него, чего быть не может, а ,значит, наш язык не регулярный. ЧТД
