Note: there is more than one right answer to many of these questions. You may receive full marks even if your solution looks very different. 1. We prove that L(G1) U L(G2) is context-free by exhibiting a CFG for it, called . Without loss of generality, we may assume that N1 and N2 are distinct, i.e., have no intersection. If not, we may consistently rename the non-terminals of one of the grammars to establish this. Let Sigma = Simga1 U Sigma2, let N = N1 U N2 U {S}, where S is a new symbol (not in N1 nor N2). Let P = P1 U P2 U {S -> S1 | S2}. A string w belongs to L(G1) U L(G2) iff S1 =>* w under G1 or S2 =>* w under G2. The latter are derivable under G from S because S => S1 =>* w and/or S => S2 =>* w. 2. G1: <{a,b},{S,X,Y},{S -> X Y, X -> a b | a X b, Y -> c | c Y},S> G2: <{a,b},{S,X,Y},{S -> X Y, X -> a | a X, Y -> b c | b Y c},S> L(G1) = {a^n b^n c+ | n >= 1}, L(G2) = {a+ b^n c^n | n >= 1}. So L(G1) ^ L(G2) = {a^n b^n c^n | n >=1}, which is not context-free. 3. (a) There are two: (1) S | |- S - 3 |- Op - + - S |- S - 1 |- Op - x - S - 2 (2) S | |- S | |- S - 3 | |- Op - + | |- S - 1 |- Op - x |- S - 2 (b) Yes. It assigned the two trees in (a) to 3+1x2. (c) No. See (d). The grammar presented there assigns one parse to every string in L(G), and assigns parses to only the strings of L(G). (d) <{0,1,2,3,+,-,x,/,(,)},{S, Op},P,S>, where P = {S -> Term TermOp S | Term, Term -> Factor FactorOp Term | Factor, Factor -> Num | ( S ), Num -> 0 | 1 | 2 | 3, TermOp -> + | -, FactorOp -> x | /}. 4. G = , where P = { s0_i -> tji s1_i | in E } U { s0_i -> tji | in E and s1_i in F } U { epsilon | if 1 in F} 5. <{a,b,c,d},{S,X,Y},P,S>, where P = {S -> X Y, X -> a b | a X b, Y -> c d | c Y d} 6. <{a,b,c,d},{S,X},P,S>, where P = {S -> a X d | a S d, X -> b c | b X c} 7. <{a,b,c,d},{S},P,S>, where P = {S -> EvenNM, EvenNM -> a OddNM d | a OddM d, OddNM -> a EvenNM d | a EvenM d, OddM -> b c | b EvenM c, EvenM -> b OddM c} 8. {a^i b^n c^j | i,j >= 1, i+j=n} = {a^i b^i b^j c^j | i,j >= 1}, so the answer to this is the same as for Question 5, substituting a -> a, b -> b, c -> b, d -> c. 9. <{a,b},{S},{S -> epsilon | a S b | b S a | S S},S> [a modification of this that does not generate the empty string is also acceptable] 10. "The intersection of a CFL and a regular language is always context-free." This is the fact that we are allowed to assume. By contraposition, if the intersection of L with a regular language is not context-free, then L was not context-free to begin with. a*b*c* is a regular expression, and the intersection of its language with L is a^n b^n c^n, which is not context-free. So L is not context-free.