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