Grammar - Hierarchy of grammar (Chomsky)


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

Recommended Pages
Card Puncher Data Processing
Automaton (State Machine)

Automaton (State Machine) Automata theory is the study of abstract computing devices or machines. The word automata (the plural of automaton) comes from the Greek word αὐτόματα, which means...
Grammar Different Structural Trees For The Same Expression
Language - (Grammar | Syntax | Lexicon)

Grammar in the context of a compiler. Ie how to define it. grammar section In processing computer languages, semantic processing generally comes after syntactic processing, but in some cases semantic...
Language - Context Free Grammar (CFG)

A context-free grammar is: a set of instructions called grammar rules (known as production rules or production) that describe all possible strings in a given formal language without context ...

Share this page:
Follow us:
Task Runner