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\,.$$

  • $\begingroup$ 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! $\endgroup$ – Charles Carmichael Apr 8 at 17:31
  • 1
    $\begingroup$ @CharlesCarmichael Correct. Each step of a derivation from a grammar involves choosing one instance of a non-terminal symbol and replacing just that one instance. Thinking that you replace all of them simultaneously is a common mistake. $\endgroup$ – David Richerby Apr 8 at 17:33
  • $\begingroup$ Thank you for the help!! $\endgroup$ – Charles Carmichael Apr 9 at 7:47

Your Answer

