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 as is the same as the number of bs, based on the idea of a counter. Can we use a similar counter in this case?

b. {xcw | S = {a, b, c};  w, x 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.  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
Hint: it may be easier to create a parse tree first.

b.      Convert G  to a string-pushing PDA DG; show a state diagram for DG. It will have one reduce transition for each terminal symbol and one shift transition for each rule.

c.       Show an accepting computation for DG over input string (a + b) * a + b, as a sequence of transitions. Show the configurations between each transition as well.
Hint: use the leftmost derivation from step (a) to guide you in choosing which shift transition to use next.

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 DG for w? Please explain.

Problem 3.  Simple PDAs

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

  1. It has a single accept state qaccept
  2. It empties its stack before accepting
  3. 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, qo, F>", and refer to these variables as needed.