states n. Now consider the string x consisting of 'a's followed by 'b's.

As M reads in x, there must be some state in the machine that is repeated as it reads in the first series of 'a's, since there are 'a's and only n states by the pigeonhole principle. Call this state S, and further let d be the number of 'a's that our machine read in order to get from the first occurrence of S to some subsequent occurrence during the 'a' sequence. We know, then, that at that second occurrence of