0

Do we need to cover all the cases or just one of them?

For instance, for $L = a^ib^jc^id^j$, the proof is uvw can't contain both a and $c$ and $b$ and $d$, but we don't cover all the cases, for instance uvw can contain as and bs, bs and cs, cs and ds. Don't we have to prove that it never ever works? No matter what string we pick?

Davide Giraudo
  • 172,925
george
  • 1

1 Answers1

0

The pumping lemma states that

If $\mathcal{L}$ is context-free, then for all strings $\omega$ longer than some $N$ there is at least one way to split it into $\omega = \omega_1\omega_a\omega_2\omega_b\omega_3$ ($\omega_a$ or $\omega_b$ non-empty, $\omega_a\omega_2\omega_b$ has length $\leq N$) such that for all $n$ also $\omega_1\omega_a^n\omega_2\omega_b^n\omega_3 \in \mathcal{L}$

To find a counter-example, you thus have to show that

For every $N$ there is a string $\omega$ with length at least $N$ such that for every partitioning $\omega = \omega_1\omega_a\omega_2\omega_b\omega_3$ ($\omega_a$ or $\omega_b$ non-empty, $\omega_a\omega_2\omega_b$ has length $\leq N$) there is some $n$ with $\omega_1\omega_a^n\omega_2\omega_b^n\omega_3 \notin \mathcal{L}$

Imagine this as the following game, where you want the pumping lemma to fail, and I want it to hold.

  1. I give you a length $N$
  2. You give me a string $\omega$ larger than $N$
  3. I pick a partitioning $\omega = \omega_1\omega_a\omega_2\omega_b\omega_3$
  4. You pick an $n$. If $\omega_1\omega_a^n\omega_2\omega_b^n\omega_3 \notin \mathcal{L}$, you win, otherwise I win.

If you can show that there's a strategy for your choices in this game with which you always win, no matter what choices I take, then you have refuted that pumping lemma and proved the language to be not context-free.

fgp
  • 21,050