In theoretical computer science, automata theory is the study of mathematical objects called abstract machines or automata and the computational problems that can be solved using them. Automata comes from the Greek word αὐτόματα meaning "self-acting".
The figure at right illustrates a finite state machine, which belongs to one well-known variety of automaton. This automaton consists of states (represented in the figure by circles), and transitions (represented by arrows). As the automaton sees a symbol of input, it makes a transition (or jump) to another state, according to its transition function (which takes the current state and the recent symbol as its inputs).
Automata theory is also closely related to formal language theory. An automaton is a finite representation of a formal language that may be an infinite set. Automata are often classified by the class of formal languages they are able to recognize.
Automata play a major role in theory of computation, compiler design, parsing and formal verification.
Read more about Automata Theory: Automata, Variant Definitions of Automata, Automata Theory, Classes of Automata, Applications, Automata Simulators, Connection To Category Theory
Famous quotes containing the word theory:
“No one thinks anything silly is suitable when they are an adolescent. Such an enormous share of their own behavior is silly that they lose all proper perspective on silliness, like a baker who is nauseated by the sight of his own eclairs. This provides another good argument for the emerging theory that the best use of cryogenics is to freeze all human beings when they are between the ages of twelve and nineteen.”
—Anna Quindlen (20th century)