CSE 237, Homework 6: PDAs
Dina Q Goldin, Spring 2006
due 3/15/05 in class

Problem 1. Chomsky Normal Form

Show that, if G is a CFG in Chomsky Normal Form, then for any string w in L(G) of length n >= 1, exactly 2n-1 steps are required for any derivation of w.

We have  the following two languages:

a. The set of strings over the alphabet {a, b, c} with twice as many b's as a's.

b. {xcw | S = {a, b, c};  w, x are strings over the alphabet {a, b}; w^R is a substring of x}

For each language, show the state diagrams of the corresponding PDAs. Try to make your PDAs as elegant as possible; do not convert from CFG to PDA. Name your states and provide a short description of what each state represents. 

1. Write a CFG G_RE whose language is the set of regular expressions over {a, b, c}. Make sure your grammar is unambiguous and obeys proper operator precedence.
   Hint: strings such as w = "a (b U c)*" are in L(G_RE ); w has length 7

2. Show a parse tree and a leftmost derivation in G_RE for the string w = "a (b U c)*"

Problem 4.  Converting CFG to PDA

1. Convert your G_RE  from problem 3 to an equivalent PDA M_RE, using the algorithm we saw in class. Show a state diagram for M_RE and number the transitions.
   

2. Show an accepting computation for "a (b U c)*" in your PDA, as a sequence of configurations. Under each configuration (except final one) indicate the number of the the transition you are about to apply, and whether it's shift or reduce.
   Hint: Whenever the top of your stack has an output symbol, you have to reduce; otherwise (if it's a variable) you have to shift. The shift transitions in this computation should use the same sequence of substitution rules as the leftmost derivation in Problem 3b.