# 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. Commented Apr 12, 2019 at 0:53
• A DFA accepts some word (its language is non-empty) if some accepting state is reachable from the initial state. Commented Apr 12, 2019 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? Commented Sep 2, 2020 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.
Commented Sep 2, 2020 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. Commented Sep 2, 2020 at 19:44