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