Suppose that $A$ and $B$ are DFAs. We know that there is some DFA $M$ such that $L(M) = L(A) \bigtriangleup L(B)$, the symmetric difference. Also, we can construct this $M$ by some Turing machine $N$. But can we ensure that $N$ has the following form?

  • $N$ consists of (i) a read-only input tape, (ii) a work tape that is log-space with respect to $|\langle A, B\rangle|$, and (iii) a one-way, write-only, polynomial-time output tape.

This really comes down to showing that this kind of TM can construct DFAs for $L(A) \cup L(B)$ and $L(A) \cap L(B)$. But it's not clear to me how this would work.

Any help is appreciated.

  • $\begingroup$ To clarify, is $\bigtriangleup$ supposed to mean the symmetric difference? (Or something else?) $\endgroup$ – dkaeae Apr 9 '19 at 11:39
  • $\begingroup$ @dkaeae Yes, that's right. $\endgroup$ – CuriousKid7 Apr 9 '19 at 13:31

Don't construct machines for $L(A)\cap L(B)$ and $L(A)\cup L(B)$. Use a variant of the product construction for those two automata to directly construct an automaton for symmetric difference. Because of the way the product construction works, you don't need to store much intermediate data at all: essentially the algorithm is just a couple of for loops and, with at most $n$ states to loop through, you only need $\log n$ bits to hold the value of the loop counter.

  • $\begingroup$ I don’t see how this variant would work. $\endgroup$ – CuriousKid7 Apr 9 '19 at 16:06
  • $\begingroup$ The product construction for union says "If one or both of the automata accepts, accept"; for intersection, it says "If both automata accept, accept"; for symmetric difference, it says "________________". $\endgroup$ – David Richerby Apr 9 '19 at 16:09
  • $\begingroup$ Right, but how could we reduce this to two for loops? $\endgroup$ – CuriousKid7 Apr 9 '19 at 16:13
  • $\begingroup$ @CuriousKid7 Ah, OK. Suppose the states of the first machine are $1, \dots, n$ and the states of the second are $1, \dots, m$. You need to construct a state $(i,j)$ for each combination. $\endgroup$ – David Richerby Apr 9 '19 at 16:18
  • 1
    $\begingroup$ @CuriousKid7 Not on a Turing machine, no, because you need to look up the values of $\delta_1(\sigma, i)$ and $\delta_2(\sigma,j)$ and that requires reading through the input tape to find the right entries. But that's not a problem. $\endgroup$ – David Richerby Apr 9 '19 at 16:58

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.