Next: Han's elaboration
Up: Regular Sets Continued
Previous: Regular Sets Continued
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.
root
6/8/1998