How to XOR automata? [closed]

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 XOR y XOR z = ((x|y)(~x|y)|z) (~((x|y)(~x|y))|z). This is way too complicated and time consuming to draw. Isn't there another way?

• This sounds like a homework problem. This forum is for research-level questions. Nov 11 '14 at 18:52
• I'm sorry if my question offended you.
– Xpl0
Nov 11 '14 at 19:03

I guess the main reason why you could not find anything about this is that it is rarely needed (and can be reduced to the better-known boolean operations, as you noted). Checking language equivalence of two automata is close, but there you don't necessarily want to compute the symmetric difference exactly, just check whether it is empty.

One way of improving on the complicated expression is by computing the product of the automata as you would for intersection, but with an accepting condition given by the XOR of those of the original automata. That is, if your automata are $P_1,\dots,P_n$, where $P_i=(S_i,s_i^0,F_i,\tau_i)$ with sets of states $S_i$, initial states $s_i^0$, sets of final states $F_i$ and transition functions $\tau_i:S_i\times A\to S_i$ (assuming the same alphabet $A$ for simplicity), your product is $(S, s^0, F, \tau)$, where

• $S=S_1\times\dots\times S_n$,
• $s=(s_1^0,\dots,s_n^0)$,
• $F$ contains $(s_1,\dots,s_n)$ iff the number of $i$ with $s_i\in F_i$ is odd,
• $\tau((s_1,\dots,s_n),a) = (\tau_1(s_1,a),\dots,\tau_n(s_n,a))$.

The only thing which differs from the usual product is the acceptance condition, reflecting the boolean combination of languages you want (here XOR instead of conjunction).

• Thank you for such a detailed and well written answer! So you are saying to AND the 3 automata, but adjust the accepting conditions accordingly, right? The problem is, the DFAs have 5, 3, and 7 states. Wouldn't that mean I'd have to draw 5x3x7=105 states?
– Xpl0
Nov 11 '14 at 18:26
• @Xpl0 Not necessarily. You build your states when needed. You start with the initial (triple-)state, and for every possible input, you add a transition to the proper (triple-)state, adding it if it does not already exist. Then you repeat for each new state you add. When all new states have been thus processed, you are finished, and whatever state was not added is not needed. It may be much less than the 105 upperbound of your example. Nov 13 '14 at 10:01