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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Удалено содержимое страницы)
(Упрощение доказательства нерегулярности примера: новая тема)
Строка 1: Строка 1:
 +
== Упрощение доказательства нерегулярности примера ==
  
 +
В данном примере мы хотели доказать, что выполнение леммы о накачке не свидетельствует о том, что язык - регулярный, для этого был приведён пример нерегулярного языка, для которого лемма выполнена. Однако доказательство нерегулярности довольно трудное, я предлагаю более простой вариант, который будет яснее.
 +
 +
Предположим, что язык - регулярный, тогда для него существует ДКА. Подадим на него n+1 строку вида ab^i где i от 1 до n+1, согласно принципу Дирихле хотя бы 2 слова должны попасть в одно и то же состояние. Пусть это слова ab^k, ab^l, тогда если мы подадим на автомат слова ab^k c^k  и ab^l c^k, то они также попадут в одно состояние, однако ab^k c^k принадлежит языку, а ab^l c^k - не принадлежит (противоречие) => наш язык не регулярный. ЧТД

Версия 21:13, 30 июня 2020

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

В данном примере мы хотели доказать, что выполнение леммы о накачке не свидетельствует о том, что язык - регулярный, для этого был приведён пример нерегулярного языка, для которого лемма выполнена. Однако доказательство нерегулярности довольно трудное, я предлагаю более простой вариант, который будет яснее.

Предположим, что язык - регулярный, тогда для него существует ДКА. Подадим на него n+1 строку вида ab^i где i от 1 до n+1, согласно принципу Дирихле хотя бы 2 слова должны попасть в одно и то же состояние. Пусть это слова ab^k, ab^l, тогда если мы подадим на автомат слова ab^k c^k и ab^l c^k, то они также попадут в одно состояние, однако ab^k c^k принадлежит языку, а ab^l c^k - не принадлежит (противоречие) => наш язык не регулярный. ЧТД