CS46 — Homework 5


CFG Pumping Lemma, Closure properties
Written solutions to problems 3.5.2bc, 3.5.8, and two of the following four problems: 2.3.3, 3.4.3, 3.5.5, and 3.5.10 are due at the beginning of class Thursday Feb 25.
Lab: Chomsky Normal Form
Read pages 151-154 and devise an algorithm to convert a grammar to Chomsky Normal Form (CNF). You may represent grammar rules in a text file as follows: 
( )

S: S1
S1: ( S1 ) S1
S1: E
The first row contains a space separated list of terminals. Rules are specified by L: R1 R2 R3 ... where L is the left hand side and the right hand side consists of terminals and non-terminals separated by spaces. Terminals will always be a single character, but non-terminals may consist of multiple characters (e.g., S1). Your program should output a new grammar in a similar format above in CNF. Python dictionaries and list manipulations are your friends again.