computer science assignment

1)      Let G be the grammar

S → SAB | AB | λ

A → aA | a

B → bB | b

(a)  Give a leftmost  derivation  of aabaabb.

(b)  Draw the parse tree for the derivation  in part  (a).

(c) Show that  this grammar  is ambiguous.

(d)  What  is the shortest  string  derivable using this grammar?

2)  Use the construction given in class for converting  a context-free  grammar  to a pushdown automaton to give a pushdown  automaton that  recognizes the lan- guage of the following grammar.  The alphabet is {a, b, c}. .

S → aSb | A A → bAc | B B → a

3) Let M be the Turing machine with Σ = {0, 1} defined by the following transition function:

Assume the machine starts  in state  qO   looking at the first input  symbol on the tape.  E indicates  a blank on the tape.

(a)  Draw the state  diagram  for M .

(Problem  6 continues on the next page.)

(b)  Trace  the computation for the  input  string  01100100. (Use machine con- figurations for the trace.)

(c) Trace  the computation for the  input  string  00000000. (Use machine con- figurations for the trace.)

(d)  Describe the  result  of a computation by M .  That  is, what  function  does

M compute?