1
$\begingroup$

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.

$\endgroup$
2
  • 2
    $\begingroup$ Remove picture and try to improve details and formatting. $\endgroup$
    – Mr. Sigma.
    Dec 15, 2018 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, 2018 at 22:12

1 Answer 1

1
$\begingroup$

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$

$\endgroup$
5
  • 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, 2018 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, 2018 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, 2018 at 9:48
  • $\begingroup$ You don't get to choose $x$ at all. $\endgroup$ Dec 16, 2018 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, 2018 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.