# 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 | $\text{TM}$ (recognizer) | Type 0: Unrestricted |

Recursive | $\text{TM}$ (decider) | Type 0: Unrestricted |

Context Sensitive | LBA (bounded $\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.