0
$\begingroup$

I looked through many sources which give this as an example for cfl. It also makes sense according to this: Properties of CFL

But it fails the pumping lemma test. Let's take n=5. According to the Pumping Lemma, we can decompose s into uvxyz like: u=0, v=0, x=0,y=01, z=111

If we pump it, it clearly fails. So, is 0^n1^n context free or not?

$\endgroup$
1
  • $\begingroup$ You don't get to choose the pumping length and you don't get to choose the decomposition. $\endgroup$
    – Steven
    Nov 13, 2023 at 10:12

1 Answer 1

2
$\begingroup$

You have just shown that the given language does not meet the condition of the pumping lemma for $n=5$ and one particular decomposition.

To conclude that $L$ is not context free you need to show that the language does not meet the condition of the pumping lemma for some word of sufficiently large length $n$ and all decompositions of such word (within the constraints of the pumping lemma).

It turns out that the words of $L = \{0^n 1^n \mid n \ge 0\}$ admit a valid decomposition as soon as $n \ge 1$. Here is a decomposition of $0^5 1^5$ into $uvxyz$ that can be pumped: $u=0^4$, $v=0$, $x=\varepsilon$, $y=1$, $z=1^4$.

This is not surprising, since $L$ is indeed context-free as the argument in your question shows.

$\endgroup$
1
  • $\begingroup$ Thank you for the response. I was unaware of the fact that the language had to be proven against every decomposition for a length n. I was taught something different. Your answer has really cleared up things for me. $\endgroup$ Nov 13, 2023 at 16:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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