Class Notes (835,600)
CPSC 313 (6)
Lecture

# Unit Productions

1 Page
126 Views

School
Department
Computer Science
Course
CPSC 313
Professor
Philipp Woelfel
Semester
Winter

Description
February 27, 2012 Unit Productions 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: 0 (1) Let P = ;. (2) Add all productions A ! ▯ in P, where ▯ 2 = V ,
More Less

Related notes for CPSC 313
Me

OR

Join OneClass

Access over 10 million pages of study
documents for 1.3 million courses.

Join to view

OR

By registering, I agree to the Terms and Privacy Policies
Just a few more details

So we can recommend you notes for your school.