• Main page

1.4.2 A few more corollaries

1. ℳ if it accepts anything at all, will accept a string of length less than |ℳ|.
2. If ℳ accepts even one string that has more characters than ℳ has states will accept arbitrarily long strings.

The Pumping Lemma is a wonderful illustration of the power of The Pigeonhole Principle. If you have n + 1 pigeons and only n pigeonholes to put them in the at least one pigeonhole will have more than one pigeon in it. The pigeonhole principle sounds too obvious to be worth noting, but the pumping lemma shows that it is very fertile.