# Is it possible to prove Language L context-free? [duplicate]

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.

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

Thank you!

• 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. – David Richerby Dec 10 '16 at 8:42
• @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\}$. – Hendrik Jan Dec 10 '16 at 14:08
• 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! – 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.

• Grammar done, proof pending. – 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.

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