Homework #2 FAQ

Problem #3

Question: Did we cover this stuff?
Answer: Sorry; as per the email message to the class mailing list, this problem is cancelled, but we advise you to work it and check your answer against the solution sheet after the material is covered (hopefully on 1/24). If you didn't get that message, you are not on the cs154-all@lists list and should subscribe immediately.

Problem #5

Question: Can't I just use the identity that the symmetric difference of L and M is (L intersect complement(M)) union (complement(L) intersect M)? Then, I could claim that because the regular languages are closed under union, intersection, and complement, they are closed under symmetric difference.
Answer: That's a valid argument, but the statement of the question warns you not to use it. Our intent was to have you go through the ``product automaton'' construction in the reader, prove the (easy) induction that this construction works, and then figure out how to make the product automaton accept the symmetric difference by choosing its set of accepting states right.

Problem #6

Question: How about a hint.
Answer: Awww... OK. Start with a DFA for L. The DFA for L/a is exactly the same except that the set of accepting states is different. Can you figure out which should be the accepting states?