title: Pumping lemma to show that `{a^n b^m | n=km for k in N}` is not regular
body: <p>How am I supposed to prove that <code>L={a^n b^m | n=km for k in N}</code> is not a regular language using the pumping lemma?</p>
  
  <p>I started with taking a word <code>w</code> in <code>L</code>, <code>w=a^n b^m</code> with <code>n=km</code> for some <code>k</code> in <code>N</code>.
  There are three possible decompositions for <code>w</code>:</p>
  
  <ol>
  <li><code>a^i * a^j * a^(n-i-j) b^m</code></li>
  <li><code>a^i * a^(n-i) b^j * b^(m-j)</code></li>
  <li><code>a^n b^i * b^j * b^(m-i-j)</code></li>
  </ol>
  
  <p>Pumping the middle part in point 2) will result in a mixed up word, which is clearly not in <code>L</code>, but I can't figure out why 1) can't give you a good decomposition:</p>
  
  <p>Let's say you pump <code>a^j</code> <code>x</code> times. Then the amount of a's in the new word will be <code>i+xj+n-i-j = n+(x-1)j</code>. We know <code>n=km</code> for some <code>m</code>. We have to show that there exists an <code>x</code> such that the new word is not in <code>L</code>. But let's assume <code>j=m</code> (This is certainly possible, since <code>n=km</code> there is always a sufficient amount of a's, except when <code>k=0</code>, but then we get a trivial case). Then <code>n+(x-1)j = km+(x-1)m = m(n+x-1)</code> which is of the form <code>{a^n b^m | n=km for k in N}</code> for all <code>x</code>. So for each <code>w</code> we have a decomposition <code>uvz</code> such that <code>u v^i z</code> is in <code>L</code> for all <code>i</code>. Thus, by the pumping lemma, <code>L</code> is regular. </p>
  
  <p>What am I missing?</p>
  
  <p>EDIT: The formulation of the Pumping lemma given:</p>
  
  <blockquote>
    <p>Let <code>L</code> be a regular language accepted by a DFA with <code>k</code> states. Let <code>w</code> be any word in <code>L</code> with length <code>&gt;= k</code>. Then <code>w</code> can be written as <code>u v z</code> with <code>|uv| &lt;=k</code>, <code>v&gt;0</code> and <code>u v^i z</code> in <code>L</code> for all <code>i&gt;=0</code></p>
  </blockquote>