AUTOMATA THEORY

body of physical and logical principles underlying the operation of any electromechanical device (an automaton) that converts information from one form into another according to a definite procedure. Real or hypothetical automata of varying complexity have become indispensable tools for the investigation and implementation of systems that have structures amenable to mathematical analysis. The information supplied to an automaton, called the input, as well as that delivered by it, called the output, may be encoded as a string of discrete symbols or characters, such as binary digits, or it may take the form of continuously variable quantities, such as electrical voltages, temperatures, mechanical forces, or positions of rotary shafts. Either input or output may be used to alter the internal state of the devicethus modifying the procedurewhile it is operating. A number of the diverse topics addressed by automata theory can be related to the operation of a Turing machine, an automaton imagined to scan a movable tape. As this machine reads each symbol, it performs some action prescribed by its current internal state. The Turing machine was the prototype of the electronic digital computer. Appropriate Turing machines have been invoked for the analysis of the consistency and completeness of systems of mathematical axioms and theorems and for the study of the structure of languages, pattern recognition, and artificial intelligence. body of physical and logical principles underlying the operation of any electromechanical device (an automaton) that converts information from one form into another according to a definite procedure. Real or hypothetical automata of varying complexity have become indispensable tools for the investigation and implementation of systems that have structures amenable to mathematical analysis. An example of a typical automaton is a pendulum clock. In such a mechanism the gears can assume only one of a finite number of positions, or states, with each swing of the pendulum. Each state, through the operation of the escapement, determines the next succeeding state, as well as a discrete output, which is displayed as the discrete positions of the hands of the clock. As long as such a clock is wound and its operation is not interfered with, it will continue to operate unaffected by outside influences except the effect of gravity on the pendulum. More general automata are designed to respond to changes in external conditions or to other inputs. For example, thermostats, automatic pilots of aircraft, missile guidance systems, telephone networks, and controls of certain kinds of automatic elevators are all forms of automata. The internal states of such devices are not determined solely by their initial state, as is the case of the pendulum clock, but may be determined by an input from a human operator, from another automaton, or by an event or series of events in the environment. A thermostat, for instance, has an on or off state that depends on the temperature. The best known general automaton is the modern electronic computer, the internal states of which are determined by the data input and which operates to produce a certain output. Bayard Rankin R.J. Nelson Additional reading Daniel I.A. Cohen, Introduction to Computer Theory, rev. ed. (1991), provides an introduction to automata, formal languages, and Turing machines at the undergraduate level. J.E. Pin, Varieties of Formal Languages, rev. and updated ed. (1986; originally published in French, 1984), introduces the theory of finite automata and regular languages. A readable introduction to automata theory as a formal theory of systems is M.W. Shields, An Introduction to Automata Theory (1987). Marvin L. Minsky, Computation: Finite and Infinite Machines (1967); and R.J. Nelson, Introduction to Automata (1967), are comprehensive elementary introductions to automata theory. Michael A. Arbib, Theories of Abstract Automata (1969); and Boleslaw Mikolajczak (ed.), Algebraic and Structural Automata Theory (1991; originally published in Polish, 1985), are more advanced introductions. Jir Admek and Vera Trnkov, Automata and Algebras in Categories (1990), develops automata theory and category theory together. Samuel Eilenberg, Automata, Languages, and Machines, 2 vol. (197476), provides a centralized presentation of important topics in automata theory and formal language theory. Martin Davis, Computability & Unsolvability (1958); H. Rogers, Theory of Recursive Functions and Effective Computability (1967, reissued 1987); George S. Boolos and Richard C. Jeffrey, Computability and Logic, 3rd ed. (1989); J. Glenn Brookshear, Theory of Computation: Formal Languages, Automata, and Complexity (1989); and Robert I. Soare, Recursively Enumerable Sets and Degrees: A Study of Computable Functions and Computably Generated Sets (1987), are concerned with the concepts of Turing computability and the theory of recursive functions.C.E. Shannon and J. McCarthy (eds.), Automata Studies (1956), contains some of the original basic material concerning neural nets and automata with unreliable components or with random elements. Michael Chester, Neural Networks: A Tutorial (1993), is an elementary introduction and survey. Franoise Fogelman Souli, Yves Robert, and Maurice Tchuente (eds.), Automata Networks in Computer Science (1987), introduces automata networks and gives applications. Eric Goles and Servet Martnez, Neural and Automata Networks (1990), focuses on dynamical neural networks and reviews important results with applications to statistical physics.Pl Rujn, Cellular Automata and Statistical Mechanical Models, Journal of Statistical Physics, 49(12):139222 (1987), introduces cellular automata in connection with lattice models. Kumpati S. Narendra and Mandayam A.L. Thathachar, Learning Automata (1989), is a technical introduction. Norbert Wiener et al., Differential Space, Quantum Systems, and Prediction (1966), discusses the automaton and its environment in the sense of prediction theory and gives reference to other literature in this area as well as the area of computable probability spaces. Good accounts of automata theory and its relations to switching theory are Michael A. Harrison, Introduction to Switching and Automata Theory (1965); and S.T. Hu, Mathematical Theory of Switching Circuits and Automata (1968). A good introduction to machine decomposition theory is J. Hartmanis and R.E. Stearns, Algebraic Structure Theory of Sequential Machines (1966). Noam Chomsky, Formal Properties of Grammars, in R. Duncan Luce, Robert R. Bush, and Eugene Galanter (eds.), Handbook of Mathematical Psychology, vol. 2 (1963), pp. 323418, is a well-respected survey of the field of automata and generative grammars. Articles presenting approaches to languages and automata from very general mathematical points of view are Seymour Ginsburg and Sheilah Greibach, Abstract Families of Languages, Memoirs of the American Mathematical Society, 87:132 (1969); and Gene F. Rose, Abstract Families of Processors, Journal of Computer and System Sciences, 4:193204 (1970). J. Richard Bchi, Finite Automata, Their Algebras and Grammars: Towards a Theory of Formal Expressions (1989), presents a centralized discussion of automata theory considering automata as algebras. Bayard Rankin R.J. Nelson The Editors of the Encyclopdia Britannica