Not always easy to find the repeat

For some fsa the first repeat is much harder to find and is very dependent on which string you are trying. For example, take the fsa below. It accepts a string if it is a binary number divisible by three. With the String 1100 (12 in decimal (8+4)), the first repeated state is state 0. With the string 1001 (9 in decimal (8+1)), the first repeated state is state 1. With the string 10101 (21 in decimal (16+4+1)), the first repeated state is state 2. Run each of these if you haven't already.

An import item to notice is that just by looking at the string, it can be hard to tell where the repeat actually is. For the previous strings here they are with the first possible y portion underlined: 1100, 1001, 10101. Of course each of these strings has more than one place where the string can be repeated or eliminated besides just the first one. Also, you can't just choose any old place to repeat the string and still have the string be accepted. For eample 110 is in the language, but 11010 is not. The only way to know for sure where a portion of the string can be repeated is to look at the fsa and find a repeated state.

This applet requires the Java Plug-In version 1.3.

Pumping 9