Grammar - Hierarchy of grammar (Chomsky)

1 - 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.

3 - 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>

4 - Documentation / Reference

code/compiler/hierarchy.txt ยท Last modified: 2018/10/25 21:42 by gerardnico