In a recent test, I was asked to recognize if the below language is context free:

$\qquad\displaystyle L = \{0^{n+m}1^{n+m}0^m \mid n,m \geq 0\}$

I think it is context free, and can be accepted by below context free grammar, where $S$ is the start symbol and $Y$ is a non-terminal:

$\qquad S \to S0 \mid Y$

$\qquad Y \to 0Y1 \mid \epsilon$

However, my answer was considered wrong and that the language $L$ is not context free.

I'm confident about my answer, but the response has got me confused. Is my understanding correct? Please let me know if I've missed something.

  • $\begingroup$ Your grammar accept a super-set of L (for instance 0100 is not in L and generated by S->S0->S00->Y00->0Y100->0100). $\endgroup$ Commented Jan 13, 2014 at 12:31
  • $\begingroup$ Oh..thanks! My grammar hasn't captured the fact that the initial 0s1s have to be equal , but also more in number than the trailing 0s.. $\endgroup$
    – sanjeev mk
    Commented Jan 13, 2014 at 12:36
  • 2
    $\begingroup$ You may want to check our reference questions and many similar questions on the site (e.g. formal-languages+context-free). Disclaimer: this may lead to fading confidence. $\endgroup$
    – Raphael
    Commented Jan 13, 2014 at 13:02
  • 1
    $\begingroup$ Pumping Lemma should suffice for this one, no? $\endgroup$
    – G. Bach
    Commented Jan 14, 2014 at 3:16

1 Answer 1


You can use Ogden's lemma. Choose the word $w = 0^p1^p0^p$ for large enough $p$, and mark the rightmost $0^p$. Ogden's lemma gives you a decomposition $w = uxyzv$ with $xz$ pumpable and containing at least one marked point. Since $xz$ contains a $0$, it can't contain a $1$, as otherwise $ux^2yz^2v \notin 0^*1^*0^*$. A simple case analysis now leads to a contradiction.


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.