Chomsky Hierarchy

This describes an aspect of syntax, originally defined by Noam Chomsky, relating classes of languages with their corresponding grammars and machines:

Language Grammar Machine Example Production Rules
Regular language Regular grammar
  • Right-linear grammar
  • Left-linear grammar
Deterministic or nondeterministic finite-state acceptor a* A -> aB,
A -> a
Context-free language Context-free grammar Nondeterministic pushdown automaton anbn A -> r
Context-sensitive language Context-sensitive grammar Linear-bounded automaton anbncn AAB -> ArB
Recursively enumerable language Unrestricted grammar Turing machine Any computable function (No restrictions)

These languages form a strict hierarchy, with greater expressive powers in the lower entries of the table.