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

Discover More
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 ...
Card Puncher Data Processing
What is an 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 self-acting An automaton consists...

Share this page:
Follow us:
Task Runner