Finding the repeat

If we look at the fsa's we can find the repeat. How? By looking for a repeatable state.

Basically, if we follow along as the fsa runs, sooner or latter, it will come to a state it has been too before.

This will always happen at least once if the number of symbols on the input string is greater or equal to the number of states in the machine. In the below example it will happen when State 1 is reached the second time.

This applet requires the Java Plug-In version 1.3.

In the above example, the y portion of the string can be repeated as many times as wanted. It can also be entirely skipped.

Pumping 5