Class Notes (835,600)
Canada (509,275)
CPSC 313 (6)

Unit Productions

1 Page
Unlock Document

Computer Science
CPSC 313
Philipp Woelfel

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

Log In


Join OneClass

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

Sign up

Join to view


By registering, I agree to the Terms and Privacy Policies
Already have an account?
Just a few more details

So we can recommend you notes for your school.

Reset Password

Please enter below the email address you registered with and we will send you a link to reset your password.

Add your courses

Get notes from the top students in your class.