This question already has an answer here:

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?


marked as duplicate by Raphael Dec 15 '15 at 10:04

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 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. Dec 14 '15 at 20:38

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.