Give a question: Language L= {a^n b^(n+m) a^m}, where both n and m are >=0. Is L context-free or not.

If the answer is yes, can I use the following PDA to prove it?

Since {a^n b^(n+m) a^m}={a^n b^n b^m a^m}, in the PDA, we first push n a's onto the stack. Then, we pop n a's from the stack by reading n b's. Next, we push m b's onto the stack, and we pop m b's from the stack by reading m a's. Finally, the strings will be accepted in q5.

enter image description here

Conversely, if the language is not context-free, should i use pumping lemma to prove it?

Thank you!

  • 3
    $\begingroup$ Please see our reference questions on how to prove that a language is context-free or not context-free. Check to see if the PDA you propose really does accept the language; if it does, the language is context-free. The pumping lemma is the natural first thing to try to prove that a language isn't context free. So I don't see any clear question, here. You have methods to try, so try them. $\endgroup$ – David Richerby Dec 10 '16 at 8:42
  • $\begingroup$ @DavidRicherby It actually is one of the examples in the answers to the reference question you quote, up to a simple renaming of one of the letters: $\{a^kb^lc^m\mid l=m+k\}$. $\endgroup$ – Hendrik Jan Dec 10 '16 at 14:08
  • $\begingroup$ Welcome to Computer Science! The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! $\endgroup$ – Raphael Dec 10 '16 at 19:01
S → AB  
A → aAb | ε  
B → bBa | ε

This will be the Grammar for that language which follows the context free grammar rules, so the language generated will be CFL.

  • $\begingroup$ Grammar done, proof pending. $\endgroup$ – Raphael Dec 10 '16 at 19:01

If the answer is yes, can I use the following PDA to prove it?

Yes you can. Context-free languages are the languages generated by context-free grammars but also those accepted by push-down automata. So, if you are not explicitly asked to do so, then there is no need to rewrite your PDA into a CFG.

Also note that there exist procedures to transform a PDA into a CFG (or vice versa). This will usually not give you an elegant grammar, but a guaranteed answer. From your notation of your PDA I guess you use Sipser's book. He describes a method that ties the moment where a symbols is pushed on the stack is tied to the same symbol being popped.


The language as you told is a union 2 languages (one for a^nb^n and other one is a^mb^m). As cfls are closed under union even your language is regular. I did not understand your pda notation to validate it.

  • $\begingroup$ So this language is not context-free? $\endgroup$ – Gareth Lam Dec 10 '16 at 8:18
  • 4
    $\begingroup$ This is not union, but rather concatenation. $\endgroup$ – Yuval Filmus Dec 10 '16 at 8:24
  • 2
    $\begingroup$ And the language certainly is not regular. $\endgroup$ – David Richerby Dec 10 '16 at 8:43

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