Обращение теоремы о накачке

[Профессор Снэйп]

Задача довольно простая, но всё же.

Скажем, что для языка $L \subseteq \Sigma^\ast$ выполнено свойство $\mathrm{Pump}(L)$, если существует $n \in \mathbb{N}$ такое, что для любого слова $w \in L$ длины $\geqslant n$ существует разложение $w = xyz$ с непустым словом $y$, для которого длина $xy$ не превосходит $n$ и все слова $xy^iz$ при $i \in \mathbb{N}$ принадлежат $L$.

Известно, что для каждого регулярного $L$ свойство $\mathrm{Pump}(L)$ выполнено. Требуется привести пример нерегулярного $L$, для которого также выполнено $\mathrm{Pump}(L)$.

[Хорхе]

У меня чувство, что даже с однобуквенным алфавитом можно кой-чего намутить. Только вот думать лень.

-- Чт янв 13, 2011 18:45:42 --

Впрочем, чего тут думать-то: слова из одной буквы длины $k$, где $k$ -- составное; $n=1$.

-- Чт янв 13, 2011 19:04:42 --

Только вот википедия дает не такую формулировку леммы о накачке: в ней $i\ge 0$, а не $i\in \mathbb N$. Так мой пример, конечно, не подойдет.

[Профессор Снэйп]

Хорхе в сообщении #399398 писал(а):

Впрочем, чего тут думать-то: слова из одной буквы длины $k$, где $k$ -- составное; $n=1$.

Э-э-э...

1) Ноль --- тоже натуральное число, так что $i=0$ допускается и $xz$ должно быть из $L$.

2) На самом деле я недоглядел один момент в условии. В $\mathrm{Pump}(L)$ нужно добавить $|y| \leqslant n$, сейчас исправлю

-- Чт янв 13, 2011 21:07:50 --

P. S. С однобуквенным алфавитом $\mathrm{Pump}(L)$ эквивалентно регулярности $L$, так что не получится

-- Чт янв 13, 2011 21:14:00 --

Хорхе в сообщении #399398 писал(а):

Только вот википедия дает не такую формулировку леммы о накачке: в ней $i\ge 0$, а не $i\in \mathbb N$. Так мой пример, конечно, не подойдет.

(Оффтоп)

Ноль --- натуральное число!!!

[Хорхе]

Профессор Снэйп в сообщении #399421 писал(а):

2) На самом деле я недоглядел один момент в условии. В $\mathrm{Pump}(L)$ нужно добавить $|y| \leqslant n$, сейчас исправлю

Википедия говорит, что $|xy|\le n$. Возможно, это одно и то же.

(Оффтоп)

Я в Советском союзе родился, после развала коего такой бардак наступил, что я натурализацию нуля как-то прозевал.

[Профессор Снэйп]

P. S. Не знаю, насколько существенно ограничение $|y| \leqslant n$. Из доказательства оно вытекает вполне естественно, и очень удобно используется при доказательстве нерегулярности языков типа $\{ a^i b^i : i \in \mathbb{N} \}$. Заодно можно сделать и ещё одно усиление, выбирая произвольное $w \in \Sigma^\ast$ достаточно большой длины и меняя последнее условие на $w \in L \Leftrightarrow \forall i(xy_iz \in L)$. Но это, уже, по-моему, лишнее.

(Оффтоп)

Напишу доказательство, оно коротенькое.

Пусть $L$ --- регулярный язык. Тогда для некоторого $n$ он распознаётся детерминированным конечным автоматом с $n$ состояниями ("ловушечное" состояние мы тоже включаем в ДКА, если оно необходимо). Пусть $w = a_1a_2\ldots a_k \in \Sigma^\ast$ для $a_1,\ldots,a_k \in \Sigma$ и $k \geqslant n$. Пусть для $i \leqslant k$ $p_i$ --- состояние автомата, в которое он приходит из начального состояния по слову $v_i = a_1\ldots a_i$ ($v_0$ --- пустое слово). Найдутся $0 \leqslant i < j \leqslant n$, такие что $p_i = p_j$. Полагаем $x = v_i$, $y = a_{i+1}\ldots a_j$ и $z = a_{j+1}\ldots a_k$. $\qed$

-- Чт янв 13, 2011 21:31:49 --

Хорхе в сообщении #399429 писал(а):

Википедия говорит, что $|xy|\le n$. Возможно, это одно и то же.

Из $|xy| \leqslant n$ следует $|y| \leqslant n$. Насчёт эквивалентности... гм, не уверен Поправлю и этот момент (в доказательстве он легко прослеживается).

-- Чт янв 13, 2011 21:36:38 --

(Оффтоп)

Хорхе в сообщении #399429 писал(а):

Я в Советском союзе родился, после развала коего такой бардак наступил, что я натурализацию нуля как-то прозевал.

Думаю, тут не от исторического периода, а от специализации зависит. В матлогике $0$ однозначно натуральное ($0 = \varnothing$ --- наименьший конечный ординал, натуральные числа суть конечные ординалы). В алгебре/матане и т. п. --- по разному, зависит от школы/конкретного профессора :)