1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – dtldarek Oct 10 '13 at 20:10
  • $\begingroup$ Cross-posted at CS SE: cs.stackexchange.com/questions/14994/why-is-anbn-context-free $\endgroup$ – user43208 Oct 10 '13 at 20:21
2
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ $|vwx|=2$ instead of $|uvw|=2$ $\endgroup$ – user35603 Oct 10 '13 at 20:29
  • $\begingroup$ Fixed all typos. $\endgroup$ – Johannes Kloos Oct 11 '13 at 7:08
1
$\begingroup$

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} $$

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

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.