# Is this language context free?

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.

• Your grammar accept a super-set of L (for instance 0100 is not in L and generated by S->S0->S00->Y00->0Y100->0100). – AProgrammer Jan 13 '14 at 12:31
• 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.. – sanjeev mk Jan 13 '14 at 12:36
• 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. – Raphael Jan 13 '14 at 13:02
• Pumping Lemma should suffice for this one, no? – G. Bach Jan 14 '14 at 3:16

## 1 Answer

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.