2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Usually you can only use the pumping lemma to prove that a language is not context-free. $\endgroup$ – MJD Oct 3 '14 at 14:40
1
$\begingroup$

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
$\endgroup$
  • $\begingroup$ why n can't be smaller than m $\endgroup$ – Harish Oct 4 '14 at 8:27
  • $\begingroup$ I'm sorry, you were right. Of course $n < m$ is possible, it just wasn't necessary for the proof. If you have any more question feel free to ask :) $\endgroup$ – TheWaveLad Oct 4 '14 at 9:38
  • $\begingroup$ if n<m then there is possibility of vwx have only alphabet a then it leads to not a CFL $\endgroup$ – Harish Oct 4 '14 at 10:12
  • $\begingroup$ Right, but remember that this doesn't show L is not context free. You just chose one specific decomposition. But you would need to prove that there is not any decomposition at all, which you can't because L is context free. $\endgroup$ – TheWaveLad Oct 4 '14 at 10:34
  • 1
    $\begingroup$ thanks very much i understood now i have to check for all possibilities $\endgroup$ – Harish Oct 4 '14 at 10:37

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.