February 27, 2012
Unit production is a production A ! B where both sides are symbols. However,
we don’t like unit productions. We should be able to produce a grammar that has
no unit productions.
Proof. Removing Unit Productions
Let G = (V;S;▯;P)
A unit pair is a pair (A;B) 2 V x V , such that there is a sequence of unit produc-
tions A ! A !1A ! ::2 ! A ! B. ekcan ▯nd all unit pairs as follows:
(1) Create a dependency graph with vertex set V and with an edge from A to
B, if and only if P has a unit production A ! B.
(2) Output all pairs (A;B) such that there is a walk from A to B (Use depth
▯rst search from A to ▯nd all verticies B that can be reached from A).
We determine the new set of productions P as follows:
(1) Let P = ;.
(2) Add all productions A ! ▯ in P, where ▯ 2 = V ,