<p>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.</p>

<p>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</p>

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

<p>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).</p>

CC BY-SA 3.0
2014-11-11T18:26:53.783Z
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
CC BY-SA 3.0
2014-11-13T10:01:56.393Z
@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.
babou
CC BY-SA 3.0
2014-11-11T18:01:35.080Z
2014-11-11T18:01:35.080Z
Klaus Draeger
<p>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.</p>

<p>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?</p>

<p>Please help, thank you for your time!</p>

CC BY-SA 3.0
2014-11-11T18:52:23.060Z
This sounds like a homework problem. This forum is for research-level questions.
Thomas Steinke
CC BY-SA 3.0
2014-11-11T19:03:07.597Z
I'm sorry if my question offended you.
Xpl0
<automata-theory><dfa><logical-relations><nfa>
How to XOR automata?
Xpl0
# How to XOR automata?

(Asked by: username_0 on 2014-11-11)

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?

Please help, thank you for your time!

**Tags:** automata-theory, dfa, logical-relations, nfa
> **Comments:**
> **username_1**: This sounds like a homework problem. This forum is for research-level questions.  
> **username_0**: I'm sorry if my question offended you.  

---

## 1 answers

### Answer by username_2 on 2014-11-11. Score: 3 | Accepted answer

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).

> **Comments:**
> **username_0**: 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?  
> **username_3**: @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.  

---

