```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.
```