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?

  • $\begingroup$ 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$ $\endgroup$ – user41805 Jul 4 '20 at 12:42
  • 1
    $\begingroup$ 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) $\endgroup$ – 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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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