2
$\begingroup$

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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • $\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
    Commented Apr 8, 2019 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
    Commented Apr 8, 2019 at 17:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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