Викиконспекты - Вклад участника [ru]

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

2020-07-01T18:06:06Z

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

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

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

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

2020-07-01T17:17:10Z

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

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

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

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

2020-07-01T17:16:53Z

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

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

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

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

2020-07-01T17:15:35Z

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

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

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

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

2020-07-01T17:15:12Z

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

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

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

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

2020-07-01T17:14:28Z

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

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

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

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

2020-07-01T17:03:37Z

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

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

2020-07-01T16:46:04Z

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

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

Предположим, что язык - регулярный $\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$ наш язык не регулярный.

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

2020-07-01T16:42:28Z

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

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

Предположим, что язык - регулярный $\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$ наш язык не регулярный.

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

2020-07-01T16:40:47Z

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

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

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

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

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

2020-07-01T16:40:04Z

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

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

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

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