Вопрос по теории формальных языков (лемма о накачке)

0

0

Не уверен, что в тему, но всё же задам его здесь.
Итак, напоминаю. subj используется для доказательства нерегулярности языка.
Пусть L - регулярный язык. Существует константа n (зависящая от L), для которой каждую цепочку w из языка L, удовлетворяющую неравенству |w|>=n, можно разбить на три цепочки w=xyz так, что выполняются следующие условия:

1) y!=E (пустой цепочке)
2) |xy|<=n
3) Для любого k>=0 цепочка xy(K)z также принадлежит L (у(K) - итерация цепочки y K раз)

Ничего не сказано про z. Значит z может быть пустой цепочкой?

Ссылка

←	сложный вопрос по perl

perl и работа с датами

→

> Значит z может быть пустой цепочкой?

Конечно!

Мало того, x тоже может быть пустой!

Die-Hard ★★★★★
(02.07.05 22:09:03 MSD)

Кстати, на этом форуме этот вопрос, вообще говоря, оффтопик. Наверное, только Talks подойдет.

Die-Hard ★★★★★
(02.07.05 22:26:11 MSD)

Ссылка

Ответ на: комментарий от Die-Hard 02.07.05 22:09:03 MSD

Спасибо за ответ. Честно говоря, я не думал, что в Talks на него ответят, потому что публика здесь и в Talks мягко говоря разная.

anonymous
(02.07.05 22:59:23 MSD)

Ответ на: комментарий от anonymous 02.07.05 22:59:23 MSD

Господа, где можно почитать о том, о чём вы только что говорили?

PS. Я прям начал сомневаться в качестве получаемого мною образования :(

Pi ★★★★★
(03.07.05 15:30:40 MSD)

Ответ на: комментарий от Pi 03.07.05 15:30:40 MSD

Ахо, Ульман "Теория синт. анализа, перевода и компиляции", том 1, где-то в районе 152 страницы :)

phoenix ★★★★
(03.07.05 15:45:27 MSD)

Ответ на: комментарий от phoenix 03.07.05 15:45:27 MSD

10x

Pi ★★★★★
(03.07.05 15:59:12 MSD)

Ответ на: комментарий от Pi 03.07.05 15:59:12 MSD

Ещё есть "Введение в теорию автоматов, языков и вычислений" Д. Хопкрофт, Р. Мотвани, Д. Ульман. Отличается последовательностью и доступностью изложения. Сам её читаю.

anonymous
(03.07.05 17:11:36 MSD)