1
$\begingroup$

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?

$\endgroup$
0
$\begingroup$

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 is reachable from the initial state. Finally, directed reachability is in $\mathsf{NL}$ (in fact, $\mathsf{NL}$-complete).

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – davidHoooo Apr 12 at 0:53
  • $\begingroup$ A DFA accepts some word (its language is non-empty) if some accepting state is reachable from the initial state. $\endgroup$ – Yuval Filmus Apr 12 at 6:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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