Обсуждение:Доказательство нерегулярности языков: лемма о разрастании — различия между версиями
(→Упрощение доказательства нерегулярности примера) |
(→Упрощение доказательства нерегулярности примера) |
||
| Строка 1: | Строка 1: | ||
== Упрощение доказательства нерегулярности примера == | == Упрощение доказательства нерегулярности примера == | ||
| − | Предположим, что язык - регулярный $\rightarrow$ для него существует ДКА. Подадим на него 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$ наш язык не регулярный. | + | Предположим, что язык - регулярный $\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$ наш язык не регулярный. |
Версия 19:46, 1 июля 2020
Упрощение доказательства нерегулярности примера
Предположим, что язык - регулярный $\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$ наш язык не регулярный.
