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