| grammar | language | automaton | |
|---|---|---|---|
| Unrestricted | Recursively enumerable | Turing machine | |
| Context sensitive | Context sensitive | Linear bounded | |
| Context free | Context free | Nondeterministic pushdown | |
| Regular | Regular | Finite state machine | |
| Each line is a proper subset
of the line directly above it. Adapted from wikipedia:tempate:formal_languages_and_grammars |
|||
