If L 1 and L2 are languages, the symmetric difference of L1 and L 2 is the set L1L2 = {x (x L1 (the complement of L2) ) (x (the complement of L1) L2)}.

a. Prove, without constructing the cross product DFA, that if L 1 and L2 are regular, then L1 L2 is regular. This will prove that the regular languages are closed under the symmetric difference operator. Hint: look for the proof in the chapter that does not use the cross product DFA, and think about how you could express L1 L2 as a function of other set operations like union, intersection and complement.

b. If you were to construct the cross product DFA from M1 = (Q, , 1, q0, F1) and M2 = (R, , 2, r0, F2) instead of doing the proof from 5a, what would the set of accept states be (the cross product DFA is otherwise identical to the one for union and intersection)? You can use the , , , operators for sets and Q, R, F1 and F 2 from the cross product DFA to construct the accept state set.