- Right-linear grammar
- Left-linear grammar
bbcA language is a set of strings over some finite alphabet. To be well-defined, a set requires a membership criterion. Two kinds of membership criteria often used for languages are grammars and automata. Other kinds of criteria are possible, such as regular expressions and recursive functions.
Language types can be arranged according to the complexity required of the membership criterion. The following is the classic Chomsky hierarchy.
| Language | Grammar | Machine | Example |
|---|---|---|---|
| Regular language | Regular grammar
|
Deterministic or nondeterministic finite-state acceptor | a* |
| Context-free language | Context-free grammar | Nondeterministic pushdown automaton | ab |
| Context-sensitive language | Context-sensitive grammar | Linear-bounded automaton | abc |
| Recursively enumerable language | Unrestricted grammar | Turing machine | Any computable function |
If there exists a grammar of a given type for a language L, then L is no more complex than the corresponding language type. It is possible that a simpler (less powerful) grammar exists for the same language.