# Is $a^{n+m}b^{n}c^{m}$ context free?

Language:

$L = a^{n+m}b^{n}c^{m}$

As per a recent test I gave, this language is not context free.

However, I think it is.

Corresponding Grammar:

$X \rightarrow aXY \space |\space \epsilon$

$Y \rightarrow b \space | \space c$

Pushdown Automata:

Keeping pushing all $a$ to the stack, until a $b$ is scanned. Keeping popping $a$ from stack for each character scanned, until end of input.

If, after the end of input the stack is empty accept the string. Else, go to non-accepting state.

Please let me know if I'm thinking along the right lines or if I've missed something..

• Has been asked before... – Yuval Filmus Feb 3 '14 at 15:01
• @YuvalFilmus Where? – Raphael Feb 3 '14 at 16:17
• @Raphael I don't remember, and it is rather hard to search for these things. Perhaps it was $a^n b^{n+m} c^m$ rather than this language. – Yuval Filmus Feb 3 '14 at 16:27
• Yeah, neither google nor StackExchange search can take MathJax, so I couldn't find if there's a duplicate.. – sanjeev mk Feb 3 '14 at 16:48
• Actually, SE can search for LaTeX (it's just text on their end); you readily find this question which is indeed equivalent. (cc @YuvalFilmus) – Raphael Feb 3 '14 at 17:16

the corresponding grammar you gave would accept aaaabcbc. A better grammar for this problem would be

$X \rightarrow aXc$

$X \rightarrow aYb$

$X \rightarrow \lambda$

$Y \rightarrow aYb$

$Y \rightarrow \lambda$

where $\lambda$ is empty string.

• Thanks , this grammar works..I wonder why my prof thinks this language is not context free.. – sanjeev mk Feb 3 '14 at 15:02
• @sanjeevmk Who can say? But a good intuition about why this language should be context free is that it's essentially $(^m[^n]^n)^m$ with the brackets spelled in a funny way, and well-matched brackets are the stereotypical context-free language. – David Richerby Dec 14 '14 at 16:31

Hint for constructing a grammar: $a^{n+m} b^n c^m = a^m (a^n b^n) c^m$.

Hint for constructing a PDA: start with a PDA for $a^{n+m} b^{n+m}$.

As a bonus, you can try to solve both parts for the language $\{ a^{n+m+k} b^n c^m d^k : n,m,k \geq 0 \}$.