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

Question

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..

Answer 1

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.

Answer 2

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 \}$.