Our First Finite State Automaton

OK, let's skip all of the gobbledygook and get right down to business.   Below is an applet that contains a graphical representation of an FSA. At the top of the applet window you see a set of blank squares with a green triangle below the first square.  These squares can hold input for the FSA to process.  For this FSA, any string of 1s and 0s you type in the squares can be input and processed by the FSA.  Let's try it.

1. Type in any string of 1s and 0s you desire (you can only input 1s and 0s because those are the only input symbols this particular FSA can process)
2. Click Run
3. Click Step repeatedly until the entire input string has been processed
4. Click once more when the input string has been completely consumed

Let's summarize what you saw. 

• The FSA processes one input symbol on the input tape at each step.
• At the beginning of each step, a red dot is found in one of the circles.
• Each time a step is performed:
  • the FSA reads the input symbol pointed to by the triangle (the input head) .
  • the red dot moves across the arrow labeled with the symbol just read by the FSA  to the next circle pointed to by that arrow
  • the input head moves right to the next input symbol, ready to read it at the next step
• When there are no more input symbols to read and a step is attempted, the FSA stops and provides some indication of the results of its computation on the input string

Try running this FSA with the following inputs to be sure that you have a clear understanding of how the FSA functions. Each time you want to try the FSA with different inputs, you must first click the Clear button and clear the input tape.

1. 1
2. 0
3. 101
4. 1101
5. The empty string (this just means that you simply run the FSA on an empty input tape; just clear the tape, click Run, and then click Step).
6. Any other strings you desire until you understand how the FSA functions

Cool!

You probably noticed that when the red dot ended in a double circle after the FSA had processed all of the input, the dot turned green, the "Accepted" light was came on, and a great "WooHoo" rattled the speakers. On the other hand, when the red dot did not end up in a double circle after the input string had been consumed by the FSA, the dot turned gray, the "Rejected" light came on, and a frustrated "DOH!" wailed out (if not, turn on your speakers). Up until the time that all of the input was consumed, the "Processing" light remained lit. (If you didn't notice these things, be sure your speakers are turned on, try a few more input strings, and watch for these indicators.)

Yeah, way cool! But, uh, does this FSA really do anything?

OK, What Does this Finite State Automaton Really Do?

We're glad you asked, because that's the title of this subsection. And here's a question for you. What kinds of strings are accepted and what kinds are rejected by this FSA? On careful examination you will see that all strings that have an even number of 1s (including zero 1s) are accepted and all other strings (i.e., all strings containing an odd number of 1s) are rejected.

A string that has an even number of 1s is said to have even parity. Thus, we say that this FSA solves this decision problem:

Next we'll examine a few more FSA's and then try to make sense of the class of all FSA's.