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