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

3.2.2

3.2.4

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

3.3.2

3.3.3

3.3.4

Give the transition table, D, of a PDA that accepts the language { w | w Î å* and # of a’s in w £ # of b’s in w}, å = {a, b}.

3.4.1

3.4.2

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)