# Pumping Lemma for CFL – $\{ 0^{i} 1^{j} 0^{k} 1^{l} \hspace{0.2cm}| \hspace{0.2cm} i = l \hspace{0.2cm} \land j = k \}$ I was making exercices about the Pumping Lemma for CFL, and I stumbled up on this language:

$$\{ 0^{i} 1^{j} 0^{k} 1^{l} \hspace{0.2cm}| \hspace{0.2cm} i = l \hspace{0.2cm} \land j = k \}$$

I quickly made a CFG that represents that language (or so I believe):

$$S \to 0S1 \hspace{0.2cm} | \hspace{0.2cm} A \ A \to 1A0 \hspace{0.2cm} | \hspace{0.2cm} \epsilon$$

The problem is that I began to think if the Pumping Lemma would hold (it should since I have a CFG for the Language, so it must be a CFL).

(Having the Pumping Lemma in mind) I chose a word, w = $$0^{n}1^{n}0^{n}1^{n}$$. I immediately stopped because this word will not pass the Pumping Lemma (it can be used to demonstrate that $$\{ ww \hspace{0.2cm}| \hspace{0.2cm} w \in \{0,1\}^{*}\}$$, the language of duplicated words, is not a CFL, I have done it before)

Now I’m stuck with a Pumping Lemma that fails, and a CFG that produces the language and don’t now what to do. I tried to come up with a word that the grammar couldn’t produce and failed, I tried to invalidate the PL but failed (there are no restrictions that tells that the word cannot have all segments of the same size, so $$w$$ is in the language).

As far as I know If the PL holds, the language doesn’t have to be a CFL, but if it fails is absolutely unquestionable that the Language is not a CFL.

What I’m I missing? Posted on Categories proxies