**CSE
3502, Homework 5 (PDAs)**

**due 2/29/18** **at the beginning of 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
counter. Can we use a similar counter in
this case?

b. {*x***c***w* | S
= {**a**, **b**, **c**}; *w*, *x*
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. Also, *number*
each transition.

**Problem 2. Converting CFG to
PDA **

a.
Let *G _{ }* be the following CFG :

**E -> E + T | T
T -> T x F | F
F -> (E) | a | b **

Show
the leftmost derivation in G for the input string (**a + b) * a + b
**

b. Convert *G _{ } to* a string-pushing PDA

c.
Show an accepting computation for *D _{G}*
over input string (

d. Suppose
you have an input string *w* 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. Simple PDAs **

Recall that a PDAs is *simple*
if it satisfies the following three conditions:

- It has a single accept state
*q*_{accept} - It empties its stack before accepting
- No transition both pushes a symbol and pops a symbol

In class, we used diagrams to
describe how to convert a regular PDA to a simple one, in three separate steps.
Now do the same thing in the form of a *formal*
description, as a sequence of instructions for each step.

*Hint*: start each step by saying "Let
*D* be a PDA, where *D* = <*Q*, Sigma, Gamma, delta, *q _{o}*,