Pumping lemma to show that `{a^n b^m | n=km for k in N}` is not regular

0
votes

How am I supposed to prove that L={a^n b^m | n=km for k in N} is not a regular language using the pumping lemma?

I started with taking a word w in L, w=a^n b^m with n=km for some k in N. There are three possible decompositions for w:

  1. a^i * a^j * a^(n-i-j) b^m
  2. a^i * a^(n-i) b^j * b^(m-j)
  3. a^n b^i * b^j * b^(m-i-j)

Pumping the middle part in point 2) will result in a mixed up word, which is clearly not in L, but I can't figure out why 1) can't give you a good decomposition:

Let's say you pump a^j x times. Then the amount of a's in the new word will be i+xj+n-i-j = n+(x-1)j. We know n=km for some m. We have to show that there exists an x such that the new word is not in L. But let's assume j=m (This is certainly possible, since n=km there is always a sufficient amount of a's, except when k=0, but then we get a trivial case). Then n+(x-1)j = km+(x-1)m = m(n+x-1) which is of the form {a^n b^m | n=km for k in N} for all x. So for each w we have a decomposition uvz such that u v^i z is in L for all i. Thus, by the pumping lemma, L is regular.

What am I missing?

EDIT: The formulation of the Pumping lemma given:

Let L be a regular language accepted by a DFA with k states. Let w be any word in L with length >= k. Then w can be written as u v z with |uv| <=k, v>0 and u v^i z in L for all i>=0

1
regular-languagefinite-automatadfapumping-lemma

1 Answers

1
votes

A perhaps easier way to proof this is first modifying the language.

Since regular languages are closed under complement and the intersection with another regular expression.

This means that you can proof L is not a regular language by proving complement(L) is not a regular language, because if L' is a regular language, L is and vice versa. The same holds for the intersection.

It is sufficient to proof that L' is not regular as well:

L' = intersection(complement(L),a*b*})

Thus

L'={a^nb^m|n != k*m, for any k in N}

Then the proof becomes way easier because you can show for whatever part you use as the pumping lemma, if it has length l, you can pump it enough times to reach a multiple.