CPSC 313 Lecture Notes - Dependency Graph, Context-Free Grammar
22 Nov 2012
School
Department
Course
Professor
Document Summary
Unit production is a production a b where both sides are symbols. We should be able to produce a grammar that has no unit productions. Let g = (v, s, , p ) 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). Consider a leftmost derivation of w using productions from p (cid:48). If that derivation uses productions in p p (cid:48), then these are unit-rules. Whenever in a leftmost derivation a unit-rule a b is applied, the next rule that is applied is b for some (v ) . Every sequence of unit productions a a1, a1 a2, , ak 1 ak is followed by a non-unit production ak . We can replace the sequence with a b.
