Automata – Choosing a Good String for the Pumping Lemma

automata

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.

Best Answer

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

Related Question