# The language $\{ww \mid w \in \{0,1\}^{*} \}$ is not a CFL

We have proved that the language $$L = \{\omega\omega \mid \omega \in \{0,1\}^{*} \}$$ is not a CFL, and we did so by using pumping lemma. And the proof is clear to me. But I thought of the following CFG:

$$G = (\{S, S_{1} \},\{0,1\},R,S)$$ where R has the following rules:

\begin{align*} S &\rightarrow S_{1}S_{1} \mid \epsilon \\ S_{1} &\rightarrow 0S_{1} \mid 1S_{1} \mid \epsilon \end{align*}

It feels like that this CFG's language should be the language $$L$$ that I have defined above since each substitution adds the same letter on both sides. But it can't be since we can use pumping lemma on the word $$0^{l}1^{l}0^{l}1^{l}$$ (where $$l$$ is the pumping length). So either I'm not doing the substitution incorrectly, or the CFG's language contains $$L$$ and has more words that I'm not seeing currently...

Can someone help me out and point out where my mistake is?

You're assuming that, when you expand $$S\to S_1S_1$$, the two copies of $$S_1$$ must be expanded in the same way, to give two copies of some string $$w$$. But it doesn't have to be that way. For example, you could do $$S\to S_1S_1 \to 0S_1S_1 \to 0 S_1 \to 01S_1\to 01\,.$$
• Thank you for the answer! I thought the substitution was simultaneous. In other words, I thought if we substitute a letter for a variable then I had to substitute for each of it occurrence, for example: $S \rightarrow S_{1}S_{1} \rightarrow 0S_{1}0S_{1} \rightarrow 01S_{1}01S_{1} \rightarrow 0101$ Just to make it clear, even if a variable appears more than once, I can apply different grammar rule to each of its occurrence separately? Hope my question is clear! Thanks! Apr 8, 2019 at 17:31