0
$\begingroup$

I know $a^nb^n$ with $n\geq0$ is considered a context-free language, but if I try:

Using pumping length $p = 3$

$n = p$, thus we have $aaabbb$

$u =aa$ and $y = bb$

$v = a$, $w = b$ and $x=λ$, then $|vwx|=2\leq p=3$ and $|vx| = 1 \geq 1$

$uv^iwx^iy \notin L$, for instance, with $i=2$ we have: $$aaaabbb$$

I know I'm wrong in some part of the process, that's I'm attempting to 'break' the lemma, to fully understand it.

$\endgroup$
7
  • $\begingroup$ The pumping lemma states that there exists a decomposition $uvwxyz$ which can be pumped, not that every decomposition can be pumped. $\endgroup$ Apr 11, 2022 at 5:00
  • $\begingroup$ @YuvalFilmus but doesn't the lemma says that if a language fails to be pumped then it wouldn't be CFG? CFGs are excepetions on its own pumping lemma? $\endgroup$ Apr 11, 2022 at 10:29
  • $\begingroup$ No it doesn’t. It says that if a language is context-free, then every long enough word in the language is “pumbable” with respect to some decomposition. $\endgroup$ Apr 11, 2022 at 10:30
  • $\begingroup$ @YuvalFilmus I get it. About the decomposition topic, I'm pretty sure mine is supposed to fit the requirements. Doesn't it? $\endgroup$ Apr 11, 2022 at 10:37
  • $\begingroup$ Pumpability is one of the requirements. (See my answer below) $\endgroup$
    – kviiri
    Apr 11, 2022 at 10:41

1 Answer 1

1
$\begingroup$

You picked a wrong decomposition. Similarly to the pumping lemma for regular languages, the pumping lemma for context-free languages states that for every context-free language $L$, there exists some legal decomposition for every string $s$ with $|s| \geq p$ where $p$ is a pumping length of $L$.

By legal decomposition, I mean dividing $s$ into partitions $uvwxy$ such that

  • $|vx| \geq 1$
  • $|uvw| \leq p$
  • $uv^nwx^ny \in L$ for all $n \in \mathbb{N}_0$

In the case of the string $aaabbb$ with $p = 3$, a legal decomposition would be eg. $u, w, y = \epsilon$, $v = aaa$, $x = bbb$.

$\endgroup$
6
  • $\begingroup$ Could you say where my decomposition fails the criteria? I can't see it $\endgroup$ Apr 11, 2022 at 10:42
  • $\begingroup$ @AkariOozora It fails the third criterion: "pumping" the string does not result in strings of $L$ as you note yourself. If all decompositions fail at least one of the criteria, then the language cannot be pumped. $\endgroup$
    – kviiri
    Apr 11, 2022 at 10:48
  • $\begingroup$ but for languages that are not CFG they would also fail for the third criteria, wouldn't they? $\endgroup$ Apr 11, 2022 at 10:52
  • $\begingroup$ @AkariOozora For every langauge, you can produce some decomposition that fails one of the criteria, and that does not prove anything. The pumping lemma states that every sufficiently long string of any context-free language has some legal decomposition in this manner. You need to prove no legal decomposition exists, which you haven't done. $\endgroup$
    – kviiri
    Apr 11, 2022 at 10:55
  • 1
    $\begingroup$ You're using $w$ to mean two different things... $\endgroup$ Apr 11, 2022 at 11:11

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.