Задача на использование леммы о разрастании(накачке).

[Sketchy]

Здравствуйте. Затрудняюсь решить задачу, надеюсь найти тут помощь.

Условие:
Используя лемму о разрастании для регулярных языков, докажите нерегулярность языка
$\{ a^{k^n}$ | $n>0, k>2 \}$ в алфавите $\{a\}$.

Пытаясь "накачать" выражение большой длинны из данного языка сталкиваюсь с трудностями.
Насколько я понимаю, можно сколько угодно накачивать выражение, и оно будет принадлежать данному языку,
если $n=1$. То есть при $n=1$ получаем язык $a^k$, где $k>2$, который,
насколько я понимаю, регулярен.
Тогда я пытаюсь использовать метод пересечения данного в условии языка с каким-либо регулярным и доказать
нерегулярность полученного пересечения. Но я уже несколько дней не могу подобрать необходимый регулярный язык,
с которым можно было бы продуктивно пересечь язык $a^{k^n}$.
Очень надеюсь найти здесь хоть какую-нибудь помощь.

[max(Im)]

Не очень хорошо разбираюсь в этой теме, но хочу помочь, поэтому выскажу свои соображения.
Согласно лемме о накачке, приведенной в википедии, для регулярного языка существует константа $p,$ такая что для любого слова языка $w$ не короче $p$ имеется представление $w = xyz,$ причем $xy^iz \in L.$ Ну попробуем доказать от противного, поскольку имеются слова сколь большой длины в языке,
то какое бы $p$ мы не подобрали, всегда придется допускать, что слово $y$ непусто, иначе просто берем слово длиннее и оно не представимо в виде $xz.$ Таким образом, в языке $L$ должны иметься слова вида
$a^{mb + c}$ для всех натуральных $b.$ Но это невозможно, так как найдется такое $b,$ что $mb + c \ne k^n$ ни для каких $n > 0, k > 2.$ Это попробуйте доказать самостоятельно.

-- 09.04.2013, 13:34 --

Я заметил небольшую неувязку в своем доказательстве, но возможно вы немного ошиблись с условием, потому что приведенный вами язык очевидно регулярный. Так как при $n = 1,$ в него войдут все слова любой длины больше двух, а регулярность такого языка вполне очевидна. Другое дело, если $n > 1,$ тогда приведенное мной доказательство сработает.

[Sketchy]

Спасибо за помощь.
В принципе, у меня были схожие мысли по доказательству, но при $n=1$, как я и написал, это доказательство не срабатывало, так же, как и у вас.

С условием все верно, сегодня спросил преподавателя насчет этого задания. Он сказал, что необходимо использовать следствие
из леммы о накачке:
Если $L$ — бесконечный регулярный язык, то в нем найдется последовательность слов, длины которых образуют возрастающую арифметическую прогрессию.

Сейчас пытаюсь придумать, как его применить.