вопрос по теории вычислений

Есть язык L = {a^*} U {b^ja^k | j>=0, k=2^n n>=0} (j,n - целые числа). Он выполняет все условия pumping lemma (доказано), надо доказать, что он не context free Я думаю, что для этого надо доказать, что для него нельзя построить pushdown automaton Но как это доказать (мне не нужно доказательство, мне нужна идея)?
(извините за такую кашу из языков, я не знаю этих определений по-русски)

(no subject)

Знаешь, как я тебя люблю?

Записи в бортовом журнале.

В американских ВВС пилоты и механики часто общаются через записи в бортжурнале. После полета пилот записывает обнаруженные неисправности, механик реагирует на них и делает запись о проделанной работе. Иногда это выглядит примерно так...

Запрос: Левое внутреннее колесо основного шасси почти требует замены.
Ответ: Левое внутреннее колесо основного шасси почти заменено.
( Read more... )