Strings are fed into the device by means of an input tape, which is divided into squares, each one holding one symbol. The main part of the machine itself is a black box which is, at any specified moment, in one of a finite number of distinct internal states, among which we distinguish an initial state and some final states. This black box, called the finite control, can sense what symbol is written at any position of the input tape by means of a movable reading head. Initially, the reading head is placed at the leftmost square of the tape and the finite control is set in a designated initial state.
At regular intervals the automaton reads one symbol from the input tape and then enters a new state that depends only on the current state and the symbol just read. After reading an input symbol, the reading head moves one square to the right on the input tape so that on the next move it will read the symbol in the next tape square.
In our picture Q0 is the initial state, a is the first symbol to be read and the machine is set so that when an a is read in state Q0 it reaches state Q1.
This process is repeated again and again. Eventually the reading head reaches the end on the input string. The automaton then indicates its approval or disapproval of what it has read by the state it is in at the end: if it winds up in one of the set of final states the input string is considered to be accepted. The language accepted by the machine is the set of the strings it accepts.
Back to Index