| Grammar | Languages | Automaton | Production rules (constraints) |
|---|---|---|---|
| Type-0 | Recursively enumerable | Turing machine |  (no restrictions) |
| Type-1 | Context-sensitive | Linear-bounded non-deterministic Turing machine |  |
| Type-2 | Context-free | Non-deterministic pushdown automaton |  |
| Type-3 | Regular | Finite state automaton |  and  |
regular 包含right-regular和left-regular，上图是right-regular
http://en.wikipedia.org/wiki/Chomsky_hierarchy
原文：http://www.cnblogs.com/cute/p/4038321.html