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:
“A theory of the middle class: that it is not to be determined by its financial situation but rather by its relation to government. That is, one could shade down from an actual ruling or governing class to a class hopelessly out of relation to government, thinking of gov’t as beyond its control, of itself as wholly controlled by gov’t. Somewhere in between and in gradations is the group that has the sense that gov’t exists for it, and shapes its consciousness accordingly.”
—Lionel Trilling (1905–1975)