Homework #2 FAQ
Did we cover this stuff?
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.
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
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.
How about a hint.
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?