We want to construct a Turing machine $M=\{,,Q,,q,q_{\text{a}\text{c}\text{c}\text{e}\text{p}\text{t}},q_{\text{r}\text{e}\text{j}\text{e}\text{c}\text{t}}\}$ with one tape, that accepts the language $L=\{0^n{1}^{2n}|n0\}sube\{0,1{\}}^{**}$ over the alphabet $=\{0,1\}.$

We assume that, at the start of the computation, the tape head is on the leftmost symbol of the input string.

The idea is as follows.

We check whether the leftmost symbol on the tape is $0.$ If so$,$ we delete it and move the tape head to the rightmost symbol on the tape. If the leftmost symbol is $1,$ we

$3/7$

CS$3240$ Assignment $2$

Yiming Zhao

reject.

We check whether the rightmost symbol is $1.$ If so$,$ we delete it and move the tape head left by one cell. If this cell contains $1,$ we delete it and move the tape head back to the leftmost symbol and continue the above step. Otherwise, we reject.

We have tape alphabet $=\{0,1,\}$ and set of states $Q=\{q,q_{\text{a}\text{c}\text{c}\text{e}\text{p}\text{t}},q_{\text{r}\text{e}\text{j}\text{e}\text{c}\text{t}},q_0,q_1,q_2,q_3\}.$ Definitions of states are listed below.

$q,$ the start state, the tape head is on the leftmost symbol of the input string.

$q_{\text{a}\text{c}\text{c}\text{e}\text{p}\text{t}},$ the accept state.

$q_{\text{r}\text{e}\text{j}\text{e}\text{c}\text{t}},$ the reject state.

$q_0,$ we have deleted the leftmost $0$ of the current string; the tape head is moving to the right.

$q_1,$ the tape head is at the rightmost symbol, and delete it if it is $1.$

$q_2,$ we have deleted one symbol $1$ from the right. The tape head is at the left neighbor of the original rightmost $1.$ We delete it if it is $1.$

$q_3,$ we are moving the tape head to the leftmost symbol after deleting two $1$ s from the right end of the current string on the tape.

The transition function $$ is specified by the following instructions. But some instructions are missing. Please complete this machine by adding those missing transitions. Please just use the notation defined above.

$q0q_{0}R$

$q1q_{\text{r}\text{e}\text{j}\text{e}\text{c}\text{t}}$

$q_{0}0q_{0}0R$

$q_{0}1q_{0}1R$

$q_0{q}_{1}L$

$q_{1}0q_{\text{r}\text{e}\text{j}\text{e}\text{c}\text{t}}$

$q_{1}1q_{2}L$

$q_{2}0q_{\text{r}\text{e}\text{j}\text{e}\text{c}\text{t}}$

$q_2{q}_{\text{r}\text{e}\text{j}\text{e}\text{c}\text{t}}$

$q_{3}0q_{3}0L$

$q_{3}1q_{3}1L$

$q_{3}qR$