[Solved]: Is this language context free?

Problem Detail: 

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.

Asked By : sanjeev mk

Answered By : Yuval Filmus

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/19690

3.2K people like this

 Download Related Notes/Documents