Обсуждение:Доказательство нерегулярности языков: лемма о разрастании — различия между версиями
(→Упрощение доказательства нерегулярности примера: новая тема) |
(→Упрощение доказательства нерегулярности примера) |
||
| Строка 3: | Строка 3: | ||
В данном примере мы хотели доказать, что выполнение леммы о накачке не свидетельствует о том, что язык - регулярный, для этого был приведён пример нерегулярного языка, для которого лемма выполнена. Однако доказательство нерегулярности довольно трудное, я предлагаю более простой вариант, который будет яснее. | В данном примере мы хотели доказать, что выполнение леммы о накачке не свидетельствует о том, что язык - регулярный, для этого был приведён пример нерегулярного языка, для которого лемма выполнена. Однако доказательство нерегулярности довольно трудное, я предлагаю более простой вариант, который будет яснее. | ||
| − | Предположим, что язык - регулярный, тогда для него существует ДКА. Подадим на него n+1 строку вида ab^i где i от 1 до n+1, согласно принципу Дирихле хотя бы 2 слова должны попасть в одно и то же состояние. Пусть это слова ab^k, ab^l, тогда если мы подадим на автомат слова ab^ | + | Предположим, что язык - регулярный, тогда для него существует ДКА. Подадим на него 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$ - не принадлежит (противоречие) => наш язык не регулярный. |
Версия 19:40, 1 июля 2020
Упрощение доказательства нерегулярности примера
В данном примере мы хотели доказать, что выполнение леммы о накачке не свидетельствует о том, что язык - регулярный, для этого был приведён пример нерегулярного языка, для которого лемма выполнена. Однако доказательство нерегулярности довольно трудное, я предлагаю более простой вариант, который будет яснее.
Предположим, что язык - регулярный, тогда для него существует ДКА. Подадим на него 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$ - не принадлежит (противоречие) => наш язык не регулярный.
