Chomsky Hierarchy

Noam Chomsky devised a classification of grammars as a heirarchy of four grammar types: type 0 (most general) — type 3 (most restrictive). The following table indicates various language classes, some of which correspond directly to the Chomsky types, others "in between." The classes are ordered by inclusion in the sense that any language belonging to one class belongs to the class at the next level.

Notation

DFA = Deterministic Finite Automaton
NFA = Non-deterministic Finite Automaton
CFL = Context-Free Language
DCFL = Deterministic Context-Free Language
PDA = Pushdown Automaton
DPDA = Deterministic Pushdown Automaton
TM = Turing Machine
NTM = Non-determinsistic Turing Machine
LBA = Linear Bounded Automaton: NTM which cannot go beyond the input string

Language Hierarchy

Language Class Machine Grammar
Regular decided by a DFA
accepted by an NFA
Left- or Right- Linear (type 3)
DCFL decided by a DPDA LR(0)
CFL accepted by a PDA Context Free (type 2)
Context Sensitive accepted by an LBA Context Sensitive (type 1)
Recursive decided by a TM
lexicographically enumerated by a TM
Recursively
Enumerable
accepted by a TM
accepted by an NTM
enumerated by a TM
Unrestricted (type 0)

Closure Properties under set operations

closure under
Language Class union intersection complement
Regular yesyesyes
DCFL nonoyes
CFL yesnono
Context Sensitive yesyesyes
Recursive yesyesyes
Recursively
Enumerable
yesyesno


© Robert M. Kline