Log-Space Reduction $USTCON\le_L CO-2Col$

I want to show that $ USTCON\le_L CO-2Col$ (Log-Space reduction)

$ USTCON$ The $ s-t$ connectivity problem for undirected graphs is called $ USTCON$ .

Input: An undirected graph $ G=(V,E)$ , $ s,t \in V$ . Output: 1 iff $ s$ is connected to $ t$ in $ G$ .

$ CO-2Col$ A graph is $ 2$ -colorable if there is a way to color the vertices of $ G$ with $ 2$ colors, such that for every edge the two vertices on the edge are colored differently. $ CO-2Col$ is the following problem:

Input: An undirected graph $ G$ . Output: 1 iff $ G$ is NOT $ 2$ -colorable.

I know this can be solved by simply using the $ USTCON$ decision algorithm and then output a bipartite or non-bipartite graph accordingly. But is there any other reduction that actually changes the input graph?

Constructing a DFA $M$ such that $L(M) = L(A) \triangle 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) \triangle L(B)$ . 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.

Reachibility between first and last layer in grid graph in logspace

I am trying to prove that there exists logspace deterministic Turing machine that check if exists path between first row and last row in grid graph. Grid graph is matrix of $ 0s$ and $ 1s$ , the undirected edge exists between two $ 0s$ or $ 1s$ – one the left, right, up, down. Path can contains only $ 0s$ or only $ 1s$ .

For example in following graph there exists such path:

0 0 1 0 0 0 1 1 0 0 0 1 0 0 0 1 

For following there is no such path

0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1  

How to prove it ?