This describes an aspect of *(syntax), originally defined by _(Noam Chomsky), relating classes of languages with their corresponding grammars and machines:

<table border=1 cellpadding=2>
<tr>
<th>Language</th>
<th>Grammar</th>
<th>Machine</th>
<th>Example</th>
<th>Production Rules</th>
</tr>
<tr>
<td>Regular language</td>
<td>Regular grammar
  <ul>
  <li>Right-linear grammar
  <li>Left-linear grammar
  </ul></td>
<td>Deterministic or nondeterministic finite-state acceptor</td>
<td>a*</td>
<td>A -> aB,<br>A -> a</td>
</tr>
<tr>
<td>Context-free language</td>
<td>Context-free grammar</td>
<td>Nondeterministic pushdown automaton</td>
<td>a<sup>n</sup>b<sup>n</sup></td>
<td>A -> r</td>
</tr>
<tr>
<td>Context-sensitive language</td>
<td>Context-sensitive grammar</td>
<td>Linear-bounded automaton</td>
<td>a<sup>n</sup>b<sup>n</sup>c<sup>n</sup></td>
<td><sub>A</sub>A<sub>B</sub> -> <sub>A</sub>r<sub>B</sub></td>
</tr>
<tr>
<td>Recursively enumerable language</td>
<td>Unrestricted grammar</td>
<td>Turing machine</td>
<td>Any computable function</td>
<td><em>(No restrictions)</em></td>
</tr>
</table>

These languages form a strict hierarchy, with greater expressive powers in the lower entries of the table.