Say we have 3 DFAs. We know how to OR, AND, or NOT them. But how does one XOR them? There is not one single mention of this online.

$x\; \mathrm{XOR} \;y\; \mathrm{XOR} \;z = ((x|y)(\neg x|y)|z) (\neg ((x|y)(\neg x|y))|z)$. This is way too complicated and time consuming to draw. Isn't there another way?

Thank you for taking the time!

  • 1
    $\begingroup$ Note: xor is symmetric set difference. $\endgroup$ – Raphael Nov 12 '14 at 14:46
  • 1
    $\begingroup$ Thank you Raphael! What I ended up doing was ε-closure, but setting a state as accepting iff the number of accepting states it enclosed was odd. If a state had no transition for a symbol, I just assumed rejection for that state but not for the others it was grouped with. $\endgroup$ – Xpl0 Nov 12 '14 at 15:00

Note that the construction for the intersection and union ("and" and "or") of two automata is exactly the same, except for the definition of which states are accepting. The same principle applies to any Boolean combination of any finite set of languages: use the product construction and the appropriate definition of which states should be accepting.

  • $\begingroup$ Very helpful, everything made sense immediately. Thank you! $\endgroup$ – Xpl0 Nov 12 '14 at 15:00

Since the three machines are all deterministic the combined operation is not complicated at all. Run the machines in parallel, using a direct product construction like the one that is also used for intersection, and at each triple state XOR the presence of final states to verify whether the new state for the XOR product should be accepting.

  • $\begingroup$ There's not much difference between your reply and David's, but I had to pick one. I'm really grateful for your help! $\endgroup$ – Xpl0 Nov 12 '14 at 15:01
  • $\begingroup$ True: our answers were written within one minute of each other. Glad we could help. Your thanks are worth more than the credits that are at stake here. $\endgroup$ – Hendrik Jan Nov 12 '14 at 20:48

Since you are only working with DFAs, you can XOR two automata by building the cross product of the two automata and then taking as accepting states those pairs of states of which one state is an accepting state, but not both.

Note that this construction only works for DFAs in which each state has exactly one successor state for each alphabet symbol. This ensures that you always reach a state when simulating the automaton and the acceptance of a word only depends on whether this state is an end state or not. Sometimes, DFAs are defined so that each state has at most one successor state for each alphabet symbol. In this case, the construction above doesn't work anymore, because there is now a second reason why a word is not accepted: with some words no state is reached at all.

  • $\begingroup$ "In this case, the construction above doesn't work anymore" -- it does, basically. Insert an error state and use the standard construction, or carry missing transitions (i.e. rejection) over to the product automaton. $\endgroup$ – Raphael Nov 12 '14 at 11:17
  • $\begingroup$ @Raphael. Of course you can add an error state. This way you make sure that each state has exactly one successor state, and then the construction works. The point is that this is a necessary step. $\endgroup$ – Hoopje Nov 12 '14 at 12:22
  • $\begingroup$ No, it's not. The construction is easy to adapt; maybe I was not clear enough? If one of the two component automata does not have a transition for the letter, you proceed as if it rejected (i.e. include no transition for intersection; include one for union and symmetric set difference and go to the corresponding original automaton). $\endgroup$ – Raphael Nov 12 '14 at 14:46
  • $\begingroup$ Thank you Hoopje! I basically followed your instructions, just with what Raphael added. $\endgroup$ – Xpl0 Nov 12 '14 at 15:02
  • $\begingroup$ @Raphael. Then you need to know which boolean function is applied during the construction of the states, and not only when selecting which states are accepting (as is claimed in all answers to the question). $\endgroup$ – Hoopje Nov 12 '14 at 15:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.