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

  • $\begingroup$ Has been asked before... $\endgroup$ Feb 3, 2014 at 15:01
  • $\begingroup$ @YuvalFilmus Where? $\endgroup$
    – Raphael
    Feb 3, 2014 at 16:17
  • $\begingroup$ @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. $\endgroup$ Feb 3, 2014 at 16:27
  • $\begingroup$ Yeah, neither google nor StackExchange search can take MathJax, so I couldn't find if there's a duplicate.. $\endgroup$
    – sanjeev mk
    Feb 3, 2014 at 16:48
  • 1
    $\begingroup$ Actually, SE can search for LaTeX (it's just text on their end); you readily find this question which is indeed equivalent. (cc @YuvalFilmus) $\endgroup$
    – Raphael
    Feb 3, 2014 at 17:16

2 Answers 2


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.

  • $\begingroup$ Thanks , this grammar works..I wonder why my prof thinks this language is not context free.. $\endgroup$
    – sanjeev mk
    Feb 3, 2014 at 15:02
  • $\begingroup$ @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. $\endgroup$ Dec 14, 2014 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 \}$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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