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.
Other articles related to "automata theory, automata":
... One can define several distinct categories of automata following the automata classification into different types described in the previous section ... The mathematical category of deterministic automata, sequential machines or sequential automata, and Turing machines with automata homomorphisms defining ... An automata homomorphism maps a quintuple of an automaton Ai onto the quintuple of another automaton Aj ...
... features that defied convenient description with the popular formal automata theory and the contemporary parser technology of the 1980s and the 1990s ... to resemble the regular expression notation of automata theory, because automata theory provides a theoretical foundation for some aspects of the ... made about the general applicability of automata to content models ...
... Word problem for linear bounded automata · Word problem for quasi-realtime automata · Emptiness problem for a nondeterministic two-way finite state automaton · Equivalence problem for nondeterministic finite ...
Famous quotes containing the word theory:
“It makes no sense to say what the objects of a theory are,
beyond saying how to interpret or reinterpret that theory in another.”
—Willard Van Orman Quine (b. 1908)