Template:Formal languages and grammars
{{Navbox with columns
| name = Formal languages and grammars
| title = Automata theory: formal languages and formal grammars
| state = {{{state
| listclass = plainlist
| col1header = Chomsky hierarchy
| col1style = text-align: center;
| col1 =
- Type-0
- —
- Type-1
- —
- —
- —
- —
- —
- Type-2
- —
- —
- Type-3
- —
- —
| col2header = Grammars
| col2 =
- Unrestricted
- (no common name)
- Context-sensitive
- Positive range concatenation
- Indexed
- —
- Linear context-free rewriting systems
- Tree-adjoining
- Context-free
- Deterministic context-free
- Visibly pushdown
- Regular
- —
- Non-recursive
| col3header = Languages
| col3 =
- Recursively enumerable
- Decidable
- Context-sensitive
- Positive range concatenation*
- Indexed*
- —
- Linear context-free rewriting language
- Tree-adjoining
- Context-free
- Deterministic context-free
- Visibly pushdown
- Regular
- Star-free
- Finite
| col4header = Abstract machines
| col4 =
- Turing machine
- Decider
- Linear-bounded
- PTIME Turing Machine
- Nested stack
- Thread automaton
- restricted Tree stack automaton
- Embedded pushdown
- Nondeterministic pushdown
- Deterministic pushdown
- Visibly pushdown
- Finite
- Counter-free (with aperiodic finite monoid)
- Acyclic finite
| below = Each category of languages, except those marked by a *, is a proper subset of the category directly above it. Any language in each category is generated by a grammar and by an automaton in the category in the same line.
}}
{{navbox documentation}}