About
In the formal languages (of computer science and linguistics), the Chomsky hierarchy is a hierarchy of formal grammars described by Noam Chomsky in 1956.
The hierarchy describes the relations between:
- various languages
- and their kinds of formalized logic.
Articles Related
Definition
| Grammar | Languages | Automaton | Production rules (constraints)* |
|---|---|---|---|
| Type-0 | Recursively enumerable | Turing machine | <math>{\displaystyle \alpha \rightarrow \beta }</math> (where <math>{\displaystyle \alpha } </math> contains at least one non-terminal) |
| Type-1 | Context-sensitive | Linear-bounded non-deterministic Turing machine | <math>{\displaystyle \alpha A\beta \rightarrow \alpha \gamma \beta }</math> |
| Type-2 | Context-free | Non-deterministic pushdown automaton | <math>{\displaystyle A\rightarrow \gamma }</math> |
| Type-3 | Regular | Finite state automaton | <math>{\displaystyle A\rightarrow {\text{a}}}</math> and <math>{\displaystyle A\rightarrow {\text{a}}B}</math> |