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.
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$&nbsp;states to loop through, you only need $\log n$ bits to hold the value of the loop counter.