Editing Theory of computation (section)

=== Automata theory ===
{{main|Automata theory}}
{| class="wikitable"
|-
! Grammar
! Languages
! Automaton
! Production rules (constraints)
|-
| Type-0
| [[recursively enumerable language|Recursively enumerable]]
| [[Turing machine]]
| <math>\alpha \rightarrow \beta</math> (no restrictions)
|-
| Type-1
| [[context-sensitive grammar|Context-sensitive]]
| [[Linear bounded automaton|Linear-bounded non-deterministic Turing machine]]
| <math>\alpha A \beta \rightarrow \alpha \gamma \beta</math>
|-
| Type-2
| [[context-free grammar|Context-free]]
| Non-deterministic [[pushdown automaton]]
| <math>A \rightarrow \gamma</math>
|-
| Type-3
| [[regular grammar|Regular]]
| [[Finite-state automaton]]
| <math>A \rightarrow a</math><br /> and<br /><math>A \rightarrow aB</math>
|}

Automata theory is the study of abstract machines (or more appropriately, abstract 'mathematical' machines or systems) and the computational problems that can be solved using these machines. These abstract machines are called automata. Automata comes from the Greek word (Αυτόματα) which means that something is doing something by itself.
Automata theory is also closely related to [[formal language]] theory,<ref name=hopcroft-ullman>{{cite book|author =[[John Hopcroft|Hopcroft, John E.]] and [[Jeffrey D. Ullman]]  | year = 2006| title =Introduction to Automata Theory, Languages, and Computation. 3rd ed| publisher =Reading, MA: Addison-Wesley. |isbn= 978-0-321-45536-9| title-link = Introduction to Automata Theory, Languages, and Computation}}</ref> as the automata are often classified by the class of formal languages they are able to recognize. An automaton can be a finite representation of a formal language that may be an infinite set. Automata are used as theoretical models for computing machines, and are used for proofs about computability.

==== Formal language theory ====
{{main|Formal language}}
[[Image:Chomsky-hierarchy.svg|thumb|right|200px|alt=The Chomsky hierarchy|Set inclusions described by the Chomsky hierarchy]]
Formal language theory is a branch of mathematics concerned with describing languages as a set of operations over an [[Alphabet (formal languages)|alphabet]]. It is closely linked with automata theory, as automata are used to generate and recognize formal languages. There are several classes of formal languages, each allowing more complex language specification than the one before it, i.e. [[Chomsky hierarchy]],<ref>{{cite journal |doi=10.1109/TIT.1956.1056813 |s2cid=19519474 |title=Three models for the description of language |date=1956 |last1=Chomsky |first1=N. |journal=IEEE Transactions on Information Theory |volume=2 |issue=3 |pages=113–124 }}</ref> and each corresponding to a class of automata which recognizes it. Because automata are used as models for computation, formal languages are the preferred mode of specification for any problem that must be computed.