next up previous contents
Next: Ben's synopsis Up: Pumping Lemma Previous: Ben's prime number joke

Regular Sets Continued

The idea is that for all strings accepted by an FA of length greater than the number of FA states, there must be repeated substrings.

More formally, if n is the number of states in the smallest FA which accepts L, if the FA accepts strings of length m > n, there must be repeated substrings[*].