Consider the following languages:

$$ \begin{align*} L_1 &= \{ 0^p 1^q 0^r \mid p,q,r \ge 0 \}, \\ L_2 &= \{ 0^p 1^q 0^r \mid p,q,r \ge 0, \; p \neq r \}. \end{align*} $$

Which one of the following statements is false?

A. $L_2$ is context-free.

B. $L_1 \cap L_2$ is context-free.

C. $\overline{L_2}$ is recursive.

D. $\overline{L_1}$ is context-free but not regular.

Doesn't the following show that $L_2$ is context-free, and so option A should be false as well?

Assume $L_2$ is context-free. Consider the string $w = 0100 \in L_2$. Breaking $w$ into $w= uvxyz$, where $u = \epsilon$, $v = 0$, $x = 1$, $y = \epsilon$, $z = 00$, according to the pumping lemma (with $p=r=2$), $uv^2xy^2z = 00100 \in L_2$, which is false.

  • 2
    $\begingroup$ Remove picture and try to improve details and formatting. $\endgroup$
    – Mr. Sigma.
    Dec 15 '18 at 16:09
  • $\begingroup$ The homework question is about languages. You changed it to a question about grammars. That's a totally different question. $\endgroup$
    – gnasher729
    Dec 15 '18 at 22:12

The mistake in your proof is that the pumping lemma says that such a division (w=uvxyz) exists.
So in order to say $L_2$ is not context free, you have to show that for every division, you get a contradiction.

In your example we can use this division:
$u=01, \, v=00, \, x=\epsilon, \, y=\epsilon , z=\epsilon$
So for every $n \geq 0$:
$uv^nxy^nz=01(00)^n \in L_2$

  • 2
    $\begingroup$ Another mistake is that the pumping lemma only applies to words whose size is at least the pumping constant. You are assuming that the pumping constant is at most 4. $\endgroup$ Dec 16 '18 at 9:22
  • $\begingroup$ @shahaf thanks for that point. So basically pumping lemma says, it must be possible to pump a given word in language somehow, even if one division of word satisfies pumping, we can't really say whether that language is context free or not. In case no possible division allows pumping, only then language is not context free? and one more point, if language doesn't contain ^ , can x still be chosen empty (^) ? $\endgroup$ Dec 16 '18 at 9:45
  • $\begingroup$ @YuvalFilmus I agree. i just chose that for the sake of it. I could have chosen bigger word easily with same bad exploit in mind. $\endgroup$ Dec 16 '18 at 9:48
  • $\begingroup$ You don't get to choose $x$ at all. $\endgroup$ Dec 16 '18 at 9:49
  • $\begingroup$ @Ashishkakran I'll recommend checking the proof of $\{a^nb^nc^n,n \geq 0\}$ not being context free, to to get an idea of how to use the lemma correctly. $\endgroup$ Dec 16 '18 at 9:56

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.