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?