Homework #5

1.  Construct a context-free grammar for strings over {a,b} with
exactly twice as many "a"s as "b"s.

    Solution:  G = ({S,a,b}, {a,b}, R, S)
	       R = S -> e | aSaSb | aSbSa | bSaSa


2.  Consider the grammar G = ({S,A,a,b}, {a,b}, R, S)
       R = S-> AA,
	   A -> AA | AAA | a | bA | Ab

    a) Which strings of L(G) can be produced by derivations of four or fewer
       steps?

    b) Give at least four distinct derivations for the string babbab

    Solution:

       a) Consider all possible four-step derivations.  Toss out duplicates
	  at any intermediate point.  Also remove from consideration strings
	  such as AAAA which cannot be instantiated (replaced with terminals)
	  in x (in this case three) or fewer steps.  The number of nonterminals
	  at each step cannot exceed the number of steps left in the derivation.

	  S -> AA -> aA   -> aa
	  S -> AA -> aA   -> abA -> aba
	  S -> AA -> aA   -> aAb -> aab
	  S -> AA -> Aa   -> aa  (delete)
	  S -> AA -> Aa   -> bAa -> baa
	  S -> AA -> Aa   -> Aba -> aba (delete)
	  S -> AA -> bAA  -> baA -> baa (delete)
	  S -> AA -> bAA  -> bAa (delete)
	  S -> AA -> AbA  -> abA (delete)
	  S -> AA -> AbA  -> Aba (delete)
	  S -> AA -> AAb  -> aAb (delete)
	  S -> AA -> AAb  -> Aab -> aab (delete)

	  {aa, aba, aab, baa}

       b) S -> AA -> bAA -> baA -> babA -> babbA -> babbAb -> babbab
	  S -> AA -> bAA -> baA -> baAb -> babAb -> babbAb -> babbab
	  S -> AA -> AAb -> bAAb -> baAb -> babAb -> babbAb -> babbab
	  S -> AA -> AAb -> bAAb -> bAab -> bAbab -> bAbbab -> babbab

3.  Minimize the DFA defined by the machine M.
    M = ({a,b,c,d,e,f,g,h}, {0,1}, delta, a, {d})
    delta(a,0) = b	delta(a,1) = g
    delta(b,0) = g	delta(b,1) = c
    delta(c,0) = d	delta(c,1) = b
    delta(d,0) = d	delta(d,1) = d
    delta(e,0) = d	delta(e,1) = f
    delta(f,0) = a	delta(f,1) = e
    delta(g,0) = f	delta(g,1) = a
    delta(h,0) = g	delta(h,1) = d

    Solution:  Node h is not a start node nor do any transitions lead to it,
       so h is unreachable and can be deleted.  The table showing
       distinguishable states is below.

        a
	  +-+
	b |3|
	  +-+-+
	c |2|2|
	  +-+-+-+
	d |1|1|1|
	  +-+-+-+-+
	e |2|2| |1|
	  +-+-+-+-+-+
	f |3| |2|1|2|
	  +-+-+-+-+-+-+
	g | |3|2|1|2|3|
	  +-+-+-+-+-+-+
	   a b c d e f g

       From the table we see that the pairs (a,g), (b,f), and (c,e) are
    equivalent.  The minimized DFA is defined by the Machine M'.

    M' = ({a/g, b/f, c/e, d}, {0,1}, delta', a/g, {d})
    delta'(a/g, 0) = b/f	delta'(a/g, 1) = a/g
    delta'(b/f, 0) = a/g	delta'(b/f, 1) = c/e
    delta'(c/e, 0) = d		delta'(c/e, 1) = b/f
    delta'(d,   0) = d		delta'(d,   1) = d

4.  Given the grammar G = ({A,B,a,b}, {a,b}, R, S)
    R = {S -> aB | bA,
	 A -> a
	 B -> aBB | bS | b}

    a) Show a leftmost derivation of the string aaabbabbba.

    b) Show a rightmost derivation of the string aaabbabbba.

    c) Show the parse tree corresponding to a derivation of aaabbabbba.

    d) Is this grammar unambiguous?  Why or why not?

    Solution:

       a) S -> aB -> aaBB -> aaaBBB -> aaabBB -> aaabbB -> aaabbaBB ->
	       aaabbabB -> aaabbabbS -> aaabbabbbA -> aaabbabbba

       b) S -> aB -> aaBB -> aaBaBB -> aaBaBbS -> aaBaBbbA -> aaBaBbba ->
	    -> aaBabbba -> aaaBBabbba -> aaaBbabbba -> aaabbabbba

       c)             S
                   +--+--+
                   |     |
		   a     B
		    +----+-----+
		    |    |     |
		    a    B     B
		      +-+++ +--+--+
		      | | | |  |  |
	              a B B a  B  B
			| |    |  +--+
			| |    |  |  |
			b b    b  b  S
			             +--+
		                     |  |
				     b  A	
					|
					|
					a

      d) The grammar is unambiguous - every parse tree is identical.