Automata are abstract machines that are studied in theoretical computer science. They are abstract in the sense that they embody an idealized or imaginary form of computation that could be constructed in many ways. The primary application of automata is as symbol processors, that is, they process information presented to them as a string of symbols drawn from a fixed alphabet.
The simplest of these is the finite-state automaton, which consists of a set of states and a list of rules. At any point in time the finite-state automaton is in one state (called the current state), and responds to one symbol of its input (called the current symbol). Each rule specifies for each state and each possible input symbol which new state the automaton will move to. The finite-state automaton begins in a specified initial state. The current state and the current input symbol are examined: one of the rules will specify which state to move to. This state becomes the current state, and the next input symbol becomes the current symbol. The computation ends when the last input symbol has been examined and processed. The state that the finite-state automaton has reached when the computation ends is called the final state.
For example, a CD player can be modeled as a finite-state automaton with three states: "stopped," "playing," and "paused." In the "playing" state the CD is rotating and music is playing from it. In the "paused" state, the CD is rotating but music is not playing. In the "stopped" state the CD is not rotating. The CD player has input in the form of three buttons, labeled Stop, Play, and Pause. If the CD player is in the "stopped" state, the only button that works is the Play button, which moves the CD player to the "playing" state. In the "playing" state the Stop button moves the CD player to the "stopped" state, the Pause button moves it to the "paused" state, and the Play button has no effect. In the "paused" state the Play and Pause buttons move it to the "playing" state, and the Stop button moves it to the "stopped" state. The CD player begins in the "stopped" state.
The following diagram represents the states of the CD player finite-state automaton as circles. Arrows represent the transitions between states that take place when the user presses its buttons. The initial state is indicated by an arrow from upper left. To simplify the diagram, transitions that lead from a state to itself are not drawn (for example, pressing the Stop button in the "stopped" state leaves the CD player in the "stopped" state).
One important application of automata is as language recognizers. Finite-state automata are used as language recognizers by designating certain states as accept states. Those inputs for which the final state is an accept state are designated as acceptable inputs, and all others are rejected. The set of acceptable inputs is termed the language of the automaton. For example, the following finite-state automaton recognizes the language that consists of the words "dog," "frog," and "fog." The accept state is indicated by a double circle.
Not all languages can be recognized by finite-state automata. The languages that can are called regular languages. For example, we have seen evidence that the language that consists of the words "dog," "frog," and "fog" is a regular language. However, the set of palindromes--all strings of letters that read the same forwards as backwards--is not a regular language.
Computer scientists have studied and analyzed a more complicated hierarchy of automata starting with the finite-state automaton. Each type of automaton recognizes a larger language class. These consist of the pushdown automaton, the linear-bounded automaton, and the Turing machine.
The pushdown automaton consists of a finite-state automaton and a pushdown stack. The stack may have a symbol inserted at the top (pushed), or deleted from the top (popped). Unlike the finite-state automaton, it also has the ability to look at the input either forwards or backwards. The rules of the pushdown automaton have the following form. For each state, each possible input symbol, and each possible symbol at the top of the stack, a rule describes whether to look at the next or previous input symbol, which state to move to, and whether to push a symbol or pop a symbol from the stack. The languages recognized by pushdown automata are called the context-free languages. These include the palindrome language and all programming languages in common use, such as C and Java.
The linear-bounded automaton replaces the stack of the pushdown automaton with a string of symbols called the worktape that is allowed to be only a constant factor larger than the input string. The linear-bounded automaton may examine only one symbol on the worktape at a time, and may choose to overwrite that symbol with a new one. The rules of the linear bounded automaton have the following form. For each state, each possible input symbol, and each worktape symbol, a rule describes which state to move to, whether to look at the next or previous input symbol, what symbol to write over the current symbol on the worktape, and whether to look at the next or previous worktape symbol. The languages recognized by linear bounded automata are called context-sensitive languages. The language that consists of two concatenated copies of an arbitrary string of symbols is context sensitive, but not context free.
The Turing machine is like a linear-bounded automaton except the worktape can now be of any size. The Turing machine is named after the British mathematician Alan Turing, who laid the foundations of modern theoretical computer science in the 1930s before electronic computers became a reality. The languages recognized by the Turing machine are called computable languages. This is the class of languages that can be recognized on a PC, a supercomputer, or indeed any sufficiently powerful model of symbolic computation invented to date. This observation is called the Church-Turing thesis after Alan Turing and his Ph.D. thesis adviser Alonzo Church, two of its leading proponents. The following problem, called the halting problem, is not computable. Given a program (in some programming language--it doesn't matter which) and an input to that program, determine whether the program will halt on that input or enter an infinite loop.
The sequence of language classes corresponding to the classes of automata described above--regular, context free, context sensitive, and computable--are known as the Chomsky Hierarchy, named after the researcher Noam Chomsky.
This is the complete article, containing 1,069 words
(approx. 4 pages at 300 words per page).
