disprove $L = \{ a^nb^n\mid n \geq 0 \}$ is not a context-free using Pumping Lemma for Context-Free Languages

Question

I am writing something about Pumping Lemma. I know that the language $L = \{ a^nb^n\mid n \geq 0 \}$ is context-free. But I don't understand how this language satisfies the conditions of Pumping Lemma (for context-free languages)?

If $z=a^mb^m$ where $n<m$ then by Pumping Lemma $z=uvwxy$, $|vwx|\leq n$. Let $vwx$ be part of $a$ terms only then $uv^iwx^iy\in L$ implies $a^{m+2 i}b^m \in L$ which is a contradiction. I know I am doing something wrong, I want to know where I'm wrong. Do you have any explanations?

Answer 1

The Pumping Lemma says, that if $L$ is context-free, there exists $n \in \mathbb{N}$, such that for every word which is longer than $n$ there is a decomposition with

1. $|vwx| \leq n$
2. $v$ and $x$ are not both empty: $|vx| \geq 1$
3. For all natural numbers $i \in \mathbb{N}_0$: $uv^i wx^i y \in L$

So let's see we can find a word from $L = \{a^n b^n\ | n \geq 0\}$ that fulfills these conditions. If we can show that, that would not mean however that $L$ is context-free!

So let $L$ be context-free. Choose $n = 2$. Let $z = a^k b^k \in Z$ with $|z| \geq n$, so $2k \geq n$. Then you can choose the following decomposition (for example):

With $a^k = a^{k-1} a^1$, $b^k = b^1 b^{k-1}$ choose $u= a^{k-1}$, $y = b^{k-1}$ and $v = a$, $x = b$, $w = \varepsilon$. So $|vx| \geq 1$, $|vwx| = 2 \leq n$ Then

$$z = u v^i wx^i y = a^{k-1} a^i b^i b^{k-1} $$

which has exactly as many $a$'s as $b$'s.

To show that $L$ is context free, you can create a nondetermenistic pushdown automaton. Once you've found one you have shown that $L$ is context-free.

Note that you can always find a word in any context-free or regular language and decompose it so that the word does not fulfill the requirements. But that doesn't say anything. $L$ is not context-free if you can show that for every word with length of at least $n$, there is no decomposition whatsoever of this kind - not that you've found one decomposition that doesn't work.

Conclusion:

1. To show that a language is context-free, create a nondetermenistic pushdown automaton
2. To show that a language is not context free, assume it is context free and show that there for all words of minimum length $n$ there can't be any decomposition with the respective properties.
3. To show that a language is regular, create a DFA
4. To show that a language is not regular, assume it is regular and use the pumping lemma for regular languages to show that for all world of minimum length there is no decomposition with the respective properties.
5. You really need to be careful with the quantifiers ($\forall, \exists, \dots$) in the pumping lemma. It is important to understand that the pumping lemma is not an if is only if condition