# How to prove that {<M1, M2> : M1 and M2 are two DFAs and L(M1) $\neq$ L(M2)} is in NL?

My idea is to find a turing machine which recognizes this language in $$\log N$$ space, could anyone give me some clue on how to find such turing machine?

First, $$L(M_1) \neq L(M_2)$$ means that there is a string that is accepted by one of the automaton but not the other. Let's "build" an automaton $$M$$ that accepts precisely such strings, and we will then want to check whether it accepts a least one string. Then $$M$$ has states $$(q^1_i, q^2_j)$$ for each state $$q_i$$ of $$M_1$$ and $$q_j$$ of $$M_2$$. A state $$(q^1_i, q^2_j)$$ of $$M$$ is accepting if and only if $$q_i$$ is accepting in $$M_1$$ and $$q_j$$ is not accepting in $$M_2$$ or vice versa. Now, in order to tell if $$M$$ accepts a string, we need to know if there's an accepting node that is reachable from $$(q^1_0, q^2_0)$$. We can first guess such a state $$(q^1_m, q^2_n)$$ as its representation uses only a logarithmic number of bits. Then we can, one step at a time, guess a path of states from $$(q^1_0, q^2_0)$$ leading to $$(q^1_m, q^2_n)$$. Of course after each guess we need to actually verify that there is an edge in $$M$$ from the previous state to the recently guessed one. In order to do that we can always keep two states in memory, the current one and the state we just guessed as the next one, this uses logarithmic memory still.
Let $$M = M_1 \times M_2$$ be the product automaton for $$L(M_1) \Delta L(M_2)$$. Then $$L(M_1) \neq L(M_2)$$ iff some accepting state of $$M$$ is reachable from its initial state. Finally, directed reachability is in $$\mathsf{NL}$$ (in fact, $$\mathsf{NL}$$-complete).
• One would need to argue as well that the construction of a DFA for $L(M_1) \Delta L(M_2)$ can be done in $\mathrm{NL}$ as well. Is that trivial? – Bernardo Subercaseaux Sep 2 at 15:25