4
$\begingroup$

we have a Language $$\mathscr L: \{a^mb^n: m \ne n\}$$

we need to choose a good string $w$.

apparently $w = a^{n+1}m^{n}$ is not a good string.

can someone explain why?

I also found this and I thought this is highly misleading, because when I use this I get wrong answers.

How to Use the Pumping Lemma for Regular Languages When you are given a language L and are using the pumping lemma to prove that it is not regular, do this: : :

  1. Assume L is regular. If it is, then the P.L. would apply. So, there is some n such that any string longer than n, say the string x, can be broken up into substrings u; v;w such that juvj n | which means the pumping part, v, lies within the rst n characters jvj > 0 | which means there is at least one character in v uvw is the string x And uvmw is also in L for any m 0 | that is, pumping at v won't take the string out of the language. The key observation is that this is true for any suciently long x. You will pick a particular one from which you can get a contradiction.

  2. Choose some string longer than n, where n is the (unknown) value guaranteed to exist by the P.L. Choose this string with a view to what you're about to do, so you can pump it up and derive a contradiction.

  3. You know v is within the rst n characters, so take your string and pump it up (or de ate it) to get a new string.

  4. Show that this new string is not in L. Since the P.L. says it is in L if L is regular, it must be the case that L is not regular.

  5. You are done. Celebrate.

$\endgroup$
2
  • $\begingroup$ You mean $w = a^{n+1}b^n$, don't you? $\endgroup$
    – MJD
    Feb 19, 2014 at 2:46
  • $\begingroup$ You have to use the pumping lemma or you just think that it will be useful? $\endgroup$
    – sas
    Feb 19, 2014 at 2:57

1 Answer 1

5
$\begingroup$

To apply the pumping lemma to show that some language $\mathscr L$ is not regular, you play a game like this:

  1. Mr. Pumping Lemma gives you a pumping constant $p$.

  2. You pick a string $s$ of length at least $p$.

  3. Mr. Pumping Lemma divides $s$ into three parts $uvw$, subject to the restrictions that $|uv|\le p$, $|v|\ge 1$.

  4. You now "pump" the $v$ part by picking an integer $i\ne 1$ to select a word $uv^iw$. If $uv^iw$ is not in $\mathscr L$, you win. But if $uv^iw$ is in $\mathcal L$, you lose.

$\def\a{\mathtt{a}}\def\b{\mathtt{b}}$Here we want to show that $\mathscr L = \{a^nb^m\mid m\ne n\}$ is not regular. Mr. Pumping Lemma gives us $p$. Then in step 2 I think you want to pick $s=a^{p+1}b^p$. You ask why this is a bad move.

It is a bad move because then in step 3 Mr. Pumping Lemma can choose $u$ to be some, but not all of the as; say $u=\a^k, v=\a^{p+1-k}, w=\b^p$.

If he does this, then in step 4 you need to pick $i$ so that $uv^iw\notin\mathscr L$. But it's not at all clear what $i$ to pick. Once you've picked $i$, you get $uv^iw = \a^k\a^{i\cdot{p+1-k}}\b^p = \a^{k+i(p-1+k)}\b^p$.

Now this string does have the form $\a^m\b^n$, where $m=k+ik+ip-i$ and $n=p$. So to win, you need $m=n$, so $ k+ik+ip-i = p$. Solving for $i$, we get $i = \frac{p-k}{k+p-1}$. But this may not be an integer, so you may not have a winning move in step 4, and you will lose. But the game was lost back in step 2 when you made the wrong choice for $s$.

$\endgroup$
8
  • $\begingroup$ where does the p+1-k come from exactly? I thought I could choose the exponent for v. I always set v equal to a single letter. $\endgroup$
    – user539484
    Feb 19, 2014 at 3:05
  • $\begingroup$ You get to choose the exponent for $v$ in step 4, that's $i$. But before you get to do that, Mr. Pumping lemma gets to pick what $v$ is, in step 3. So suppose he picks $\def\a{\mathtt{a}}u=\a^k$; that is, $u$ is some of the initial as. And suppose he picks $v$ to be the rest of the as. You said that the string $w$ had $p+1$ as, so if $u$ contains $k$ of them, then $v$ contains the rest, which is $p+1-k$ as. $\endgroup$
    – MJD
    Feb 19, 2014 at 3:07
  • $\begingroup$ yeah... it's kinda confusing. are you saying it should work for any v? i thought that was completely irrelevant and i just had to make a string that was not in the language defined, so i would just set w such that i would just need to pump v once. $\endgroup$
    – user539484
    Feb 19, 2014 at 3:11
  • $\begingroup$ You don't get to pick $v$. Mr. Pumping Lemma takes your string $s$ and cuts it into three parts, $u,v,$ and $w$. Then you have to be able to show that no matter how he cuts up $s$, you can always come up with an $i$ that will make $uv^iw$ not part of $\mathscr L$. $\endgroup$
    – MJD
    Feb 19, 2014 at 3:13
  • 1
    $\begingroup$ also how would you make sure you would get an integer? $\endgroup$
    – user539484
    Feb 19, 2014 at 3:17

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .