Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I am struggling on this one question, where it is asking to define an XOR automata which is defined as an NFA and it is defined as the following:

N accepts the string x if the number of distinct accepting states that can be reached by a path labeled with x is odd.

I'm supposed to prove that any languages accepted by the XOR automata is regular and that any regular language can be accepted by the XOR automata.

Can anyone explain to me how I may be able to go about starting this proof? Thanks.

share|cite|improve this question
This is not what I think the usual definition of xor automaton is. (I think it is an odd number of accepting paths.) – Louis Feb 27 '13 at 14:06
up vote 1 down vote accepted

If you’re familiar with the powerset construction for converting an NFA to an equivalent DFA, a slight modification of it can be used to convert an XOR automaton to an equivalent DFA. (This PDF has more detail on the powerset construction.) In the basic powerset construction, a state $\{q_1,\dots,q_m\}$ in the DFA is an acceptor state if and only if at least one of $q_1,\dots,q_m$ is an acceptor state in the original NFA $N$. If you want to view $N$ as an XOR automaton, make $\{q_1,\dots,q_m\}$ an acceptor state in the DFA if and only if an odd number of the states $q_1,\dots,q_m$ are acceptor states in $N$.

The opposite direction is easy. A DFA $M$ is essentially an NFA in which each input labels a unique path, so a word is accepted by $M$ in the usual sense if and only if it labels an odd number of paths ending in an acceptor state: that odd number is $1$.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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