Grammar - Hierarchy of grammar (Chomsky)


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.


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>

Documentation / Reference

Powered by ComboStrap