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

Unit Productions

1 Page
126 Views
Unlock Document

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

Log In


OR

Join OneClass

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

Sign up

Join to view


OR

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.


Submit