next up previous contents
Next: Han's elaboration Up: Regular Sets Continued Previous: Regular Sets Continued

Ben's synopsis

Consider a finite state machine with ten states; god gives me a string which is 20 symbols long which results in an accept. Since there can't be a unique state for every symbol in the string, it means that I have repeated at least one state; There must be a state loop in the machine.

This means that one can construct a string of arbitrary length that will be accepted by the FA by concatenating multiple ``loop'' substrings at the appropriate point in an otherwise accepted input string.