**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 a’s is the same as the number of b’s, based on the idea of a
tally. Can we use something similar in
this case?

b. {*x***c***w*
| *x**, w are* strings over the alphabet {**a**,**
b**}; *w*^{R} 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

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

Name all the transitions as follows: T

In front of each transition, write its name.

c. Show an accepting computation in *D _{G}* for
input string “

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 *D _{G}* for

**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.