Chomsky Hierarchy

The Chomsky Hierarchy

The Chomsky Hierarchy is a classification of formal languages into four types, each corresponding to a type of automaton. Named after Noam Chomsky, it provides a complete taxonomy of computational power — from the simplest to the most powerful.

The Four Types

Type 0: Recursively Enumerable
  Machine: Turing Machine (TM)
  Grammar: Unrestricted grammars
  Example: The halting problem's language

Type 1: Context-Sensitive
  Machine: Linear Bounded Automaton (LBA)
  Grammar: Context-sensitive grammars
  Example: {a^n b^n c^n | n >= 1}

Type 2: Context-Free
  Machine: Pushdown Automaton (PDA)
  Grammar: Context-free grammars (CFG)
  Example: {a^n b^n | n >= 0}

Type 3: Regular
  Machine: Finite Automaton (DFA/NFA)
  Grammar: Regular grammars
  Example: Strings containing "01"

Hierarchy:
  Type 0 ⊃ Type 1 ⊃ Type 2 ⊃ Type 3
  (Each type is a subset of the one above it)

Key Differences

                  FA        PDA       LBA       TM
States:           Finite    Finite    Finite    Finite
Tape:             None      Stack     Linear    Infinite
Memory:           Finite    Stack     Linear    Infinite
Power:            Lowest    More      More      Highest
Recognizes:       Regular   Context-  Context-  Recursively
                  langs     free      sensitive Enumerable

Key relationships:
  Every regular language is context-free
  Every context-free language is context-sensitive
  Every context-sensitive language is recursively enumerable
  But NOT the reverse!

Grammar Forms

Each type corresponds to a restriction on the grammar's production rules:

Type 3 (Regular):
  A → aB  or  A → a  or  A → ε
  (at most one variable on the right side, must be at the end)

Type 2 (Context-Free):
  A → α
  (left side is a single variable, right side is any string)

Type 1 (Context-Sensitive):
  A → α  where |α| >= |A| = 1
  (production can't shrink the string, except S → ε)

Type 0 (Unrestricted):
  α → β
  (any production, no restrictions)

Why the Hierarchy Matters

The hierarchy tells you exactly what kind of machine you need to recognize a given language. If a language is regular, a simple DFA suffices — fast and memory-efficient. If it's context-free, you need a PDA with a stack. If it's context-sensitive, you need more power. And if it's recursively enumerable, you need a Turing machine.

This has practical implications: regular expressions (Type 3) are fast but limited. CFGs (Type 2) can parse programming languages but can't handle everything. Understanding where your problem falls in the hierarchy helps you choose the right tools.