Skip to content
Tutorials Center
My learning

Topics

Lesson 20 of 59 · Context-Free Grammars

Chomsky Normal Form and Greibach Normal Form

Learn how to convert a context-free grammar to Chomsky Normal Form and Greibach Normal Form, remove left recursion and use CNF in the CYK parsing algorithm.

A context-free grammar can have right-hand sides of any shape, which makes proofs and algorithms messy. A normal form restricts the shape of productions without losing any language (except possibly ε), so that algorithms can assume a clean, predictable structure. Two normal forms are standard: Chomsky Normal Form (CNF) and Greibach Normal Form (GNF).

Chomsky Normal Form

A grammar is in CNF when every production has one of two shapes:

  • A → B C: exactly two variables, or
  • A → a: exactly one terminal.

(Plus, if ε is in the language, the single rule S → ε, with S not appearing on any right-hand side.) Every parse tree for a CNF grammar is a binary tree: every internal node has two children, except the last level, where each node has one terminal leaf. A string of length n needs exactly 2n − 1 derivation steps, which is handy in proofs and gives us the CYK algorithm below.

Conversion algorithm

Every CFG can be converted. The steps, in a safe order:

  1. START. Add a new start variable S0 → S, so the start symbol never appears on a right side.
  2. DEL. Remove ε-productions (see simplifying CFGs).
  3. UNIT. Remove unit productions A → B.
  4. TERM. In every right side of length ≥ 2, replace each terminal a by a new variable Ya, and add Ya → a.
  5. BIN. Break right sides of length > 2: A → X1 X2 X3 ... Xk becomes A → X1 Z1, Z1 → X2 Z2, ..., ending in Zk-2 → Xk-1 Xk.

Example: S → (S)S | ε. After START, DEL, UNIT it is S0 → ( S ) S | ( S ) | ( ) S | ( ) | ... (all with nullable parts dropped). TERM and BIN produce rules like S → L X, X → S Y, Y → R S ... all of the two-variable shape.

Implementation and CYK

The CYK algorithm (Cocke-Younger-Kasami) decides whether a CNF grammar generates a string w of length n in O(n³ · |G|) time using dynamic programming. Let T[i][j] be the set of variables that derive the substring of w from position i with length j. Base: T[i][1] = {A : A → w_i}. Inductive step: A is in T[i][j] if there is a rule A → B C and a split k with B in T[i][k] and C in T[i+k][j−k]. The string is accepted if S is in T[0][n].

Python Convert a grammar to CNF and run CYK

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 rules in the printed grammar are all of the forms A → B C, A → a (the converted terminal rules Y_( → ( and Y_) → )), and the program confirms that CYK agrees with a simple counter check on every string up to length 8. CNF costs size: the conversion can square the number of rules in the worst case, but it is still polynomial.

Greibach Normal Form

A grammar is in Greibach Normal Form (GNF) if every production has the shape

A → a α

where a is a terminal and α is a (possibly empty) string of variables. Every right side begins with a terminal. This has a nice consequence: each derivation step produces exactly one terminal at the left end, so a string of length n is derived in exactly n steps. That makes GNF convenient for building top-down parsers and for converting a grammar into a pushdown automaton with no ε-moves.

GNF requires that the grammar has no left recursion: a production A → A α would let the leftmost symbol stay a variable forever.

Removing immediate left recursion

If A → A α1 | ... | A αm | β1 | ... | βn, where no βi starts with A, replace it with

TEXT
A  -> β1 | ... | βn | β1 A' | ... | βn A'
A' -> α1 | ... | αm | α1 A' | ... | αm A'

The new grammar generates the same strings but builds the repetition to the right. For E → E + T | T this gives E → T | T E', E' → + T | + T E'.

Python Eliminate immediate left recursion

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 full GNF algorithm in outline

  1. Simplify the grammar and convert it to CNF (or at least remove ε and unit productions).
  2. Number the variables A1, ..., An.
  3. For i from 1 to n: for each j < i, substitute the right sides of Aj into productions Ai → Aj γ, until every Ai production starts with a terminal or a variable Ak with k ≥ i. Then remove immediate left recursion for Ai, introducing a helper variable Bi.
  4. Now every An production starts with a terminal. Work backwards from An to A1: substitute so that each production of Ai starts with a terminal.
  5. Finally substitute into the helper variables Bi so that they also start with a terminal.

A small example: for the language {a^n b^n : n ≥ 1}, the grammar S → aSb | ab converts to GNF as

TEXT
S -> a S B | a B
B -> b

Every production begins with a terminal, and an n-symbol string takes exactly n steps. The next chapter turns a GNF grammar into a pushdown automaton: each production A → a α becomes "read a, pop A, push α".

CNF versus GNF

Feature CNF GNF
Right-hand sides two variables, or one terminal one terminal followed by variables
Parse tree binary tree each step consumes a terminal
Steps to derive a string of length n 2n − 1 n
Main use CYK parsing, proofs (pumping lemma) Top-down parsing, PDA construction

Check your understanding

Quick check · 5 questions

of 5 answered You scored / 5 · perfect!

  1. 1. Which production is allowed in Chomsky Normal Form?

    CNF allows only A → BC (two variables) and A → a (one terminal).
  2. 2. How many derivation steps does a CNF grammar need to derive a string of length n ≥ 1?

    There are n − 1 binary steps to make n leaves and n terminal steps, giving 2n − 1.
  3. 3. Why does GNF exclude left-recursive grammars?

    A production A → Aα starts with a variable, which contradicts the GNF shape A → aα.
  4. 4. What is the running time of the CYK algorithm for a string of length n?

    CYK fills a table of O(n²) cells, and each cell tries O(n) split points.
  5. 5. Which grammar is the GNF of {a^n b^n : n ≥ 1}?

    Every production begins with a terminal followed only by variables.

Summary

  • CNF: every rule is A → BC or A → a; steps START, DEL, UNIT, TERM, BIN; derivation of an n-symbol string takes 2n − 1 steps; CYK parses in O(n³).
  • GNF: every rule is A → aα (a terminal then variables); needs no left recursion; each step consumes one terminal.
  • Immediate left recursion A → Aα | β becomes A → β | βA', A' → α | αA'.
  • Both normal forms preserve the language except possibly ε.

Next: Closure Properties of CFLs and the Pumping Lemma