3
$\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$
  • $\begingroup$ You mean $w = a^{n+1}b^n$, don't you? $\endgroup$ – MJD Feb 19 '14 at 2:46
  • $\begingroup$ You have to use the pumping lemma or you just think that it will be useful? $\endgroup$ – sas Feb 19 '14 at 2:57
4
$\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$
  • $\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 '14 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 '14 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 '14 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 '14 at 3:13
  • 1
    $\begingroup$ also how would you make sure you would get an integer? $\endgroup$ – user539484 Feb 19 '14 at 3:17

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.