Обсуждение:Доказательство нерегулярности языков: лемма о разрастании — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Удалено содержимое страницы)
(Упрощение доказательства нерегулярности примера)
 
(не показано 12 промежуточных версий 2 участников)
Строка 1: Строка 1:
 +
== Упрощение доказательства нерегулярности примера ==
  
 +
Предположим, что язык - регулярный, значит, для него существует ДКА (пусть в нём $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$ тоже переходит в него, чего быть не может, следовательно, наш язык не регулярный.

Текущая версия на 02:55, 2 июля 2020

Упрощение доказательства нерегулярности примера

Предположим, что язык - регулярный, значит, для него существует ДКА (пусть в нём $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$ тоже переходит в него, чего быть не может, следовательно, наш язык не регулярный.