University of Alberta Dictionary of Cognitive Science: Finite State Automaton

In the formal study of language, logic, and computation many different information processing devices have been proposed (Hopcroft & Ullman, 1979; Parkes, 2002). In classical cognitive science, the most famous of these is the Turing machine (Turing, 1936). However, alternatives to the Turing machine have also been described. One such alternative to a Turing machine is called a finite state automaton. Like a Turing machine, a finite state automaton can be described as a machine head that interacts with a set of symbols written on a ticker tape. There are two key differences between a finite state machine and a Turing machine. First, a finite state machine can only move in one direction along the tape, again one cell at a time. Second, a finite state machine can only read the symbols on the tape; it does not write new ones. The symbols that it encounters (in combination with the current physical state of the device) determine the new physical state of the device. Again, a question is written on the tape, and the finite state automaton is started. When it reaches the end of the question, the final physical state of the finite state automaton represents its answer to the original question on the tape.

It is obvious that a finite state automaton is a simpler device than a Turing machine, because it cannot change the ticker tape, and because it can only move in one direction along the tape. However, finite state machines are important information processors. Many of the behaviors in behavior-based robotics are produced using finite state machines (Brooks, 1989, 1999, 2002). It has also been argued that such devices are all that is required to formalize behaviorist or associationist accounts of psychology (Bever et al., 1968).

References:

Bever, T. G., Fodor, J. A., & Garrett, M. (1968). A formal limitation of associationism. In T. R. Dixon & D. L. Horton (Eds.), Verbal Behavior And General Behavior Theory (pp. 582-585). Englewood Cliffs, NJ: Prentice-Hall.
Brooks, R. A. (1989). A robot that walks; emergent behaviours from a carefully evolved network. Neural Computation, 1, 253-262.
Brooks, R. A. (1999). Cambrian Intelligence: The Early History Of The New AI. Cambridge, MA: MIT Press.
Brooks, R. A. (2002). Flesh And Machines: How Robots Will Change Us. New York, NY: Pantheon Books.
Hopcroft, J. E., & Ullman, J. D. (1979). Introduction To Automata Theory, Languages, And Computation. Reading, MA: Addison-Wesley.
Parkes, A. (2002). Introduction to Languages, Machines and Logic: Computable Languages, Abstract Machines and Formal Logic. London ; New York: Springer.
Turing, A. M. (1936). On computable numbers, with an application to the Entscheidungsproblem. Proceedings of the London Mathematical Society, Series 2h, 42, 230-265.

(Added September 2010)