# 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?

• Does $0^n1^n0^n1^n$ not pass the Pumping Lemma? $0^p1^p0^p1^p=0^p1^{p-1}1^n0^n0^{p-1}1^p$ – user41805 Jul 4 '20 at 12:42
• In the case of your language, if you apply the pumping lemma to $0^n1^n0^n1^n$ it doesn't mean that the pumped string must preserve the same number of letters for the four "sequences": the pumped string must only satisfy the condition $0^m1^q0^q1^m$ (m allowed to be different from q) – Vor Jul 4 '20 at 12:53

$$\{ww\mid w\in\{0,1\}^*\}$$ not being context-free does not imply every subset is also not context-free. In this case, $$0^n1^n0^n1^n$$ passes the pumping lemma, since it can be written as follows $$0^p1^p0^p1^p=0^p1^{p-1}1^n0^n0^{p-1}1^p$$.