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 ; see wikipedia: Automata Theory |