Finite Automata

Introduction: If we do not allow writing or two-way operation of the tape head, we have what has been traditionally called a finite automaton. This machine is only allowed to read its input tape and then, on the basis of what it has read and processed, accept or reject the input

This restricted machine operates by:

a)  Reading a symbol,

b)  Transferring to a new instruction, and Advancing the tape head one square to the right.

When it arrives at the end of its input it then accepts or rejects depending upon what instruction is being executed.

This sounds very simple.  It is merely a one-way, semi-literate Turing machine that just decides membership problems for a living! Let us examine one.  In order to depict one, all we need to do is jot down Turing machine instructions in one large table, leave out the write part (that was not a pun!), and add a note which indicates whether the machine should accept.  Here is an example:

Look closely at this machine.  It stays on instruction one until it reads a one. Then it goes to instruction two and accepts any input unless another one arrives (the symbol 1 - not another input).  If two or more ones appear in the input, then it ends up executing instruction three and does not accept when the input is over. And if no one’s appear in the input the machine remains on instruction one and does not accept. So, this machine accepts only inputs that contain exactly one 1.

Traditionally these machines have not had instructions but states. (Recall A. M. Turing's states of mind.)  Another way to represent this same machine is to put the next instruction or next state or goto portion under the input in a table like that in figure 1.

There is another traditional method to describe finite automata which is extremely intuitive.  It is a picture called a state graph.  The states of the finite automaton appear as vertices of the graph while the transitions from state to state under inputs are the graph edges. The state graph for the same machine also appears in figure 1.

Figure 1:

Finite automata representation(Note that the two circles that surround state two mean acceptances.)

Before continuing let's examine the computation of a finite automaton. Our first example begins in state one and reads the input symbols in turn changing states as necessary.  Thus a computation can be characterized by a sequence of states. (Recall that Turing machine configurations needed the state plus thetape content.  Since a finite automaton never writes, we always know what is onthe tape and need only look at a state as a configuration.) Here is the sequencefor the input 0001001.

Input Read: 0 0 0 1 0 0 1