CS4124 Theory of Computation


HW #5: fewer problems, but lots of parts!

Due Wednesday 13 October 1999 at 1200 hrs

Late policy: 10%/day up to 50% (weekends = 1 day)

If your paper is illegible, you will lose points





Let G be the grammar

S aB | bA

A a | aS | bAA

B b | bS | aBB

For the string aaabbabbba find a

a)   leftmost derivation

b)   rightmost derivation

c)   parse tree






Give the transition table, D, of a PDA that accepts the language { w | w * and # of as in w # of bs in w}, = {a, b}.





Consider the PDA M whose transition function is given by the following set of transitions (assume the empty stack starts with # on it):


((s, a, #), (s, 0#))

((s, a, 0), (s, 00))

((s, e, 0), (q, 0))

((s, e, #), (q, #))

((q, b, 0), (q, e))

((q, e, #), (q, e))


a)   apply the construction that derives a CFG from a PDA to get a context-free grammar G such that L(G) = L(M)

b)   present a trace of the acceptance of word aabb by pushdown automaton M

c)   present a leftmost derivation of word aabb in grammar G

d)   formulate the observed correspondence between the trace of b) and the leftmost derivation of c)