LINUX.ORG.RU

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


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 может быть пустой цепочкой?

anonymous

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

Конечно!

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

Die-Hard ★★★★★
()

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

Die-Hard ★★★★★
()
Ответ на: комментарий от Die-Hard

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

anonymous
()
Ответ на: комментарий от anonymous

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

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

Pi ★★★★★
()
Ответ на: комментарий от Pi

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

anonymous
()
Ответ на: комментарий от Pi

2Pi:

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

Pumping lemma в гугле набери.

Die-Hard ★★★★★
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.