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.