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

### Other articles related to "automata theory, automata":

**Automata Theory**- Connection To Category Theory

... 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 ...

**Automata Theory**

... 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)