Изменения

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