# Constructing a DFA $M$ such that $L(M) = L(A) \bigtriangleup L(B)$ with a kind of log-space TM

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.

• To clarify, is $\bigtriangleup$ supposed to mean the symmetric difference? (Or something else?) – dkaeae Apr 9 '19 at 11:39
• @dkaeae Yes, that's right. – 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.
• @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. – David Richerby Apr 9 '19 at 16:18
• @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. – David Richerby Apr 9 '19 at 16:58