Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I am writing somthing about Ppumping Lemma. I know that the language L = { a^nb^n| n ≥ 0 } is context-free. But I don't understand how this language satisfies the conditions of pumping lemma (for context-free languages) ?

if we pick the string s = a^pb^p, |s| > p , |vxy| < p and |vy| > 0.

it seems it will be out of the language when we pump it (pump up or down) or there is something I'm missing.

Any explanation would help.

Edit: I am applying pumping lemma to a^nb^n and it fails to stay in the language for all cases. So, why is it Context free?

share|improve this question
    
It means that for any finite-state machine that automaton would have to accept a word which is not in the language, and so it cannot recognize that language. If no finite state machine can recognize that language, then it is not regular. –  dtldarek Oct 10 '13 at 20:10
    
Cross-posted at CS SE: cs.stackexchange.com/questions/14994/why-is-anbn-context-free –  user43208 Oct 10 '13 at 20:21

2 Answers 2

up vote 2 down vote accepted

The thing is that the lemma only says that for a CFL $L$, a $p$ exists such that any string $s$ of length at least $p$ (i.e., $|s| \ge p$) can be decomposed as $s =uvwxy$ with $|vwx|<p$, $vx \neq \varepsilon$ and $uv^nwx^ny \in L$.

Now, in the example, consider $s=A^nB^n$. Take $p = 3$, $v=A$, $x=B$, $u=A^{n-1}$, $w=\varepsilon$ and $y=B^{n-1}$.

Then clearly $|vwx|=2<3$, $vx = AB \neq \varepsilon$ and $uv^mwx^my = A^{n-1}A^mB^mB^{n-1} = A^{m+n-1}B^{m+n-1} \in L$.

share|improve this answer
    
$|vwx|=2$ instead of $|uvw|=2$ –  user35603 Oct 10 '13 at 20:29
    
Fixed all typos. –  Johannes Kloos Oct 11 '13 at 7:08

The pumping lemma for CFLs says that any sufficiently long string $s$ in a CFL $\mathcal L$ can be broken up into $s=uvxyz$ such that:

  1. $|vxy| ≤ p$,
  2. $|vy| ≥ 1$, and
  3. $uv^nxy^nz$ is in $\mathcal L$ for all $n ≥ 0$.

$\def\a{{\tt a}}\def\b{{\tt b}}$ Let's suppose that your adversary $A$ claims that $\a^n\b^n$ is not a CFL, and you disagree. The proof would go like this:

  1. You give the adversary $A$ your claimed pumping constant $p$ for this language. In this case it turns out that $p=3$ works.
  2. $A$ picks $s$ with $|s| \ge p$. Let's say $A$ picks $s = \a^3\b^3$.
  3. You pick $u,v,x,y,z$ as above, with $s = uvxyz$. In this case you might choose $u = \a\a, v=\a, x=\epsilon, y=\b, $ and $z=\b\b$, as in Johannes Kloos's answer. (Now we check to make sure these choices satisfy conditions 1, 2, and 3 of the previous paragraph.)
  4. Now $A$ tries to pick $m$ such that $uv^mxy^mz\notin\mathcal L$. If $A$ can do this, you lose. If $A$ can't, you win.

Clearly for this example, whatever $m$ is chosen by $A$ in step 4, you get $uv^mxy^mz = \a\a\; \a^m\; \epsilon\; \b^m\; \b\b = \a^{m+2}\b^{m+2}$ which is in $\mathcal L$, so $A$ loses, and $A$'s claim that $\mathcal L$ is not context-free fails.

Could $A$ have defeated you by making a better choice of $s$ back in step 2? You should think about that.


The short answer to the question you asked is that $\a^n\b^n$ is a CFL because it is generated by the CFG:

$$\begin{align} S & \to \a S\b \mid \epsilon \end{align} $$

share|improve this answer
    
I didnt break it into 3 parts. |vxy| is just for middle three parts. –  user2226106 Oct 10 '13 at 20:24
    
Thanks, I misunderstood you. I have elaborated on how to use the pumping lemma for CFLs. –  MJD Oct 10 '13 at 20:34

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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