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

[katenok]

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

Comments

[drklaymen.livejournal.com]

Heh, have never seen this exercise. It's a nice example, but a bit stupid: one can prove stronger versions of the pumping lemma that this language will not satisfy. Anyway, they probably didn't show you these versions and I don't suppose you're interested in proving them yourself. ;) So here's an idea: first, it's obvious that if L is CF then so is L_1 = {ba^(2^k): k>=0} (just intersect L with ba* which is regular). Now L_1 obviously does NOT satisfy the pumping lemma.

[katenok.livejournal.com]

10x.