CSE 237, Homework 5 (PDAs)
due 10/11/17 in class

Problem 1. From a language description to a PDA

Show state diagrams of PDAs for the following languages:

a. The set of strings over the alphabet {a, b} with twice as many a's as b's.
Hint: in class, we showed a PDA when the number of as is the same as the number of bs, based on the idea of a tally. Can we use something similar in this case?

b. {xcw | x, w are strings over the alphabet {a, b}; wR is a substring of x}

Try to make your PDAs as simple and elegant as possible (do not convert from CFG to PDA). Name your states and provide a short description of what each state represents. 

Problem 2.  Converting CFG to PDA

a.       Let G  be the CFG from textbook problem 2.1 (it has 6 rules).  Show the leftmost derivation in G for the input string (a + a) * a + a.
For each substitution, underline the variable that was substituted, and indicate under it the number of the rule that was used.

b.      Convert G  to a string-pushing PDA DG; show a state diagram for DG.
Name all the transitions as follows: T1 and T2 for the first and last transition, Si for the SHIFT transition corresponding to ith rule (using the numbering from part a); Rc for the REDUCE transition corresponding to terminal c.
In front of each transition, write its name.

c.       Show an accepting computation in DG for input string (a + a) * a + a, as a chain of configurations as floows:
Show the configuration (consisting of current state, remaining input, and stack contents) at the beginning of the computation, then after each transition and until the end. Label the arrows between configurations with the transition names from step b.

d.      Suppose you have a string w in L(G) of length l, and you know that a leftmost derivation of w in G is k substitutions long.  How many transitions would be in the corresponding computation of DG for w? Explain your answer.

Problem 3. Chomsky Normal Form

Chomsky Normal Form of a CFG is defined on p. 109 (definition 2.8).

Show that if G is a CFG in Chomsky Normal Form, then for any string w in L(G) of length n ≥ 1, all derivations of w will contain exactly 2n-1 steps.