Can we show that following language is not context free using Push down automata approach?

L = {a^i b^i a^i : i>=1} 

For every a we will Push 'A' onto stack, for every b we will pop 'A' out of stack so at the end we will have a's onto stack and the input word would be empty as string would be something like aabbaa

Does it seem correct?

  • 3
    $\begingroup$ Possible dup: cs.stackexchange.com/q/265/755. That lists many ways for proving a language is not context-free, including some that don't use the pumping lemma. Is there any reason those techniques don't work here? Incidentally, what is your motivation for not using the pumping lemma? Also, we discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. $\endgroup$
    – D.W.
    Commented Dec 14, 2015 at 20:38

1 Answer 1


Your approach doesn't work. We don't know how a putative push-down automaton for the language works. What you show is that a particular PDA doesn't work, but perhaps another one does.


Not the answer you're looking for? Browse other questions tagged or ask your own question.