Editing Automata theory (section)

{{short description|Study of abstract machines and automata}}
{{Use dmy dates|date=May 2019|cs1-dates=y}}
{{Automata theory}}

[[File:DFAexample.svg|thumb|300px| The automaton described by this [[state diagram]] starts in state S<sub>1</sub>, and changes states following the arrows marked 0 or 1 according to the input symbols as they arrive. The double circle marks S<sub>1</sub> as an accepting state. Since all paths from S<sub>1</sub> to itself contain an even number of arrows marked 0, this automaton accepts strings containing even numbers of 0s.]]

'''Automata theory''' is the study of [[abstract machine]]s and [[automaton|automata]], as well as the [[computational problem]]s that can be solved using them. It is a theory in [[theoretical computer science]] with close connections to [[cognitive science]] and [[mathematical logic]]. The word ''automata'' comes from the [[Greek language|Greek]] word αὐτόματος, which means "self-acting, self-willed, self-moving". An [[automaton]] (automata in plural) is an abstract self-propelled [[computing device]] which follows a predetermined sequence of operations automatically. An automaton with a finite number of [[State (computer science)|states]] is called a finite automaton (FA) or [[finite-state machine]] (FSM). The figure on the right illustrates a finite-state machine, which is a well-known type of automaton. This automaton consists of [[State (computer science)|states]] (represented in the figure by circles) and [[Transition (computer science)|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 table|transition function]], which takes the previous state and current input symbol as its [[Parameter (computer programming)|arguments]].

Automata theory is closely related to [[formal language]] theory. In this context, automata are used as finite representations of formal languages that may be infinite. Automata are often classified by the class of formal languages they can recognize, as in the [[Chomsky hierarchy]], which describes a nesting relationship between major classes of automata. Automata play a major role in the [[theory of computation]], [[compiler construction]], [[artificial intelligence]], [[parsing]] and [[formal verification]].