Skip to content
Tutorials Center
My learning

Topics

Lesson 3 of 59 · Getting Started

Grammars and the Chomsky Hierarchy

Understand formal grammars, productions and derivations, then classify any grammar into the four Chomsky types with working Python code and examples.

A machine recognizes a language by reading a string and answering yes or no. A grammar does the opposite: it generates the strings of a language by starting from a symbol and applying rewrite rules. The two views turn out to be equivalent, and that equivalence is one of the most beautiful parts of the subject.

Formal grammars

A grammar is a four-tuple G = (V, T, P, S):

  • V: a finite set of variables (also called non-terminals), written in capitals.
  • T: a finite set of terminals, the symbols of the final strings (the alphabet), written in lowercase. V and T share no symbols.
  • P: a finite set of productions (rewrite rules) of the form α → β, where α and β are strings of variables and terminals and α contains at least one variable.
  • S: the start variable, one of V.

A derivation starts with S and repeatedly replaces a substring that matches the left side of a production with its right side. We write α ⇒ β for one step and ⇒* for zero or more steps. The language of G, L(G), is the set of all terminal strings derivable from S.

Here is a grammar for {a^n b^n : n ≥ 0}:

TEXT
S -> a S b
S -> ε

Derive aabb: S ⇒ aSb ⇒ aaSbb ⇒ aabb. Each use of the first rule adds one a and one b around the middle, and the second rule finishes the job.

Python Generate a language from a grammar

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The search expands the leftmost variable each time and stops expanding a form once it already has more terminals than the length limit. The first line shows ε, ab, aabb, aaabbb; the second shows every palindrome of length at most 3 over {a, b}.

The Chomsky hierarchy

In 1956 Noam Chomsky classified grammars by how restricted their productions are. The more restricted the rules, the simpler the language and the simpler the machine that recognizes it.

Type Name Production shape Recognized by
3 Regular A → aB or A → a (right-linear), or the left-linear mirror Finite automaton
2 Context-free A → γ (one variable on the left) Pushdown automaton
1 Context-sensitive αAβ → αγβ with γ non-empty (never shrinks) Linear bounded automaton
0 Unrestricted α → β (anything, α non-empty) Turing machine

The names say what the rules can look at. In a context-free rule the variable A is rewritten no matter what surrounds it. In a context-sensitive rule, A may be rewritten only when it sits between a specific left context α and right context β. A regular grammar is the most restricted of all: it can build a string only one symbol at a time, always at one end.

Each type contains the one above it: every regular grammar is context-free, every context-free grammar is context-sensitive (apart from the technicality of ε-rules), and every context-sensitive grammar is unrestricted. The languages form a strict nesting. For example a^n b^n is context-free but not regular, and a^n b^n c^n is context-sensitive but not context-free.

flowchart TB
    T0["Type 0: recursively enumerable<br/>Turing machine"]
    T1["Type 1: context-sensitive<br/>linear bounded automaton"]
    T2["Type 2: context-free<br/>pushdown automaton"]
    T3["Type 3: regular<br/>finite automaton"]
    T3 -->|"properly inside"| T2
    T2 -->|"properly inside"| T1
    T1 -->|"properly inside"| T0

Type 3 is the smallest class. Climbing the diagram means allowing more general productions and stronger machines.

Classifying a grammar in code

You can decide a grammar's type just by inspecting each production. The code below does so for the simple notation used above: capital letters are variables, lowercase letters terminals. It reports the most restrictive type that every rule satisfies.

Python Classify a grammar by its productions

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

This simplified checker only recognizes right-linear regular grammars and treats the start-symbol ε-rule leniently, which is enough to show the idea. A production-grade checker would also handle left-linear grammars and the exact "S → ε" exception.

Why the hierarchy matters

  • Compilers tokenize with regular languages (Type 3) and parse structure with context-free grammars (Type 2). Anything needing context, like "a variable must be declared before use", is checked in a separate step because it is not context-free.
  • Natural language processing uses context-free grammars as a first approximation, even though real languages are messier.
  • Limits: for Type 0, no algorithm can decide whether a given string belongs to L(G). That undecidability result arrives in the chapters on Turing machines.

The next lessons climb the hierarchy from the bottom, beginning with the simplest machine: the finite automaton.

Check your understanding

Quick check · 4 questions

of 4 answered You scored / 4 · perfect!

  1. 1. Which grammar type allows only one variable on the left side of every production?

    Context-free rules have the form A → γ with a single variable on the left. Regular grammars also satisfy this but are further restricted on the right side.
  2. 2. Which machine recognizes the languages of Type 1 (context-sensitive) grammars?

    Context-sensitive languages are exactly those accepted by linear bounded automata: Turing machines whose tape is limited to the length of the input.
  3. 3. Which language is context-free but not regular?

    a^n b^n is generated by S → aSb | ε but needs unbounded counting, so no finite automaton can recognize it. The other options are all regular.
  4. 4. In a derivation S ⇒ aSb ⇒ aaSbb ⇒ aabb, what is the language L(G)?

    L(G) contains only strings made entirely of terminals that can be derived from the start symbol.

Summary

  • A grammar G = (V, T, P, S) generates a language by repeatedly rewriting from the start variable.
  • The Chomsky hierarchy has four nested types: regular, context-free, context-sensitive and unrestricted.
  • Each type pairs with a machine: finite automaton, pushdown automaton, linear bounded automaton, Turing machine.
  • A grammar's type is found by checking the shape of each production.
  • The inclusions are strict: each type generates languages the previous one cannot.

Next: Applications of Automata