The Chomsky Hierarchy

Learn about the Chomsky hierarchy of formal languages and the existence of languages that are not recursively enumerable.

We'll cover the following

We can now summarize the entire hierarchy of formal languages. We emphasize “hierarchy” because each language class is a subset of the class above it. This classification originated with Noam Chomsky and is aptly called the Chomsky hierarchy. See the following table.

Language Class Recognizing Machine Grammar Type
Recursively Enumerable TM\text{TM} (recognizer) Type 0: Unrestricted
Recursive TM\text{TM} (decider) Type 0: Unrestricted
Context Sensitive LBA (bounded TM\text{TM}) Type 1: Non-contracting
Context Free PDA Type 2: Context Free
Deterministic Context Free DPDA Type 2: Context Free
Regular DFA Type 3: Right/Left Linear

Get hands-on with 1200+ tech skills courses.