# 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?

Yuval's answer describes the main component. For the sake of completeness I'll precise a couple of details.

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

• Thanks for your comment! However, I don't quite understand the part that "𝐿(𝑀1)≠𝐿(𝑀2) iff some accepting state is reachable from the initial state", could you explain a little bit of that? Thanks in advance. Apr 12 '19 at 0:53
• A DFA accepts some word (its language is non-empty) if some accepting state is reachable from the initial state. Apr 12 '19 at 6:02
• 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? Sep 2 '20 at 15:25
• @BernardoSubercaseaux, what are your thoughts? Have you tried to figure it out? If you did and got stuck, you could ask a new question. This is an exercise, so you might need to fill in some details yourself. Note that it suffices to construct it on the fly.
– D.W.
Sep 2 '20 at 16:29
• You don't need to explicitly construct the DFA. You just need to simulate oracle access to the DFA. I didn't write it here since I have already written several times in other answers. Sep 2 '20 at 19:44