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$ – AProgrammer Jan 13 '14 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 Jan 13 '14 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 Jan 13 '14 at 13:02
  • 1
    $\begingroup$ Pumping Lemma should suffice for this one, no? $\endgroup$ – G. Bach Jan 14 '14 at 3:16

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, privacy policy and cookie policy

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