Grammar - Hierarchy of grammar (Chomsky)

> Code - (Programming|Computer) Language > Computer Language - (Compiler|Interpreter) - Language translator

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

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