How to draw a Turing Machine for Even-Even

Question

A TM to accept EVEN-EVEN (a collection of all strings with an even number of a's and an even number of b's) can be based on the algorithm:

1. Move up the string, changing a’s to A’s
2. Move down the string, changing b’s to B’s

Modified algorithm: To avoid the problem of crashing on the way down the $Tape$, change the letter in the first cell to an $X$ (if it's an $a$) and to a $Y$ (if it's a $b$). This way we can recognize the left end of the tape.

So far I have this but am not sure how to implement the modified algorithm (note: the e's from start to halt mean empty):

Any help is appreciated!

Answer 1

From what I understand, your first algorithm intends to process the $a$ and $b$ inputs separately, which doesn't seem necessary. Your difficulty seems to come from formalizing a TM, which you can do in a couple ways.

Direct Conversion (Courtesy of Raphael in the comments)

You can view an NFA as TM that can not write and move only to the right. In other words, you don't have to do anything at all for the conversion, just add $R$ to transitions that consume a symbol and $N$ to $ε$-transitions, and then you basically have your equivalent TM.

Multitape Approach - Suppose we know that a multitape TM is equivalent to a TM, so we can have two tapes:

• An input tape (with a string $x\in(a|b)^*$), which we'll read through exactly once.
• A computation tape which will have one of four numbers $1$, $2$, $3$, or $4$, reflecting the state that the analogous finite automata (for which you have an image) might have. If we didn't want to expand the alphabet, we could instead have $\{\epsilon\epsilon,a\epsilon,\epsilon b,ab\}$ to indicate the parity of each letter.

As we proceed through the input, we update the computation tape accordingly: if we read an $a$, and we're in state $1$, we swtich to state $3$, etc. To reduce this back to one tape, we need another symbol $\#$ to separate tapes, perhaps $\hat{a},\hat{b}$ to designate the location of the heads and pre/append our computation tape (for which we only need two characters of space).

Formal Approach - we're going to define the set of states $Q$, the tape alphabet $\Gamma$, the blank symbol $\epsilon$, the input symbols $\Sigma$, the initial state $q_0$, the accepting states $F$ and the transition function $\delta$.

$$\langle Q=\{q_{\epsilon\epsilon},q_{a\epsilon},q_{\epsilon b},q_{ab}\},\Gamma=\{a,b\},b=\epsilon,\Sigma=\{a,b\},q_0=q_{\epsilon\epsilon},F=\{q_\epsilon\},\delta\rangle$$ $$\delta= \begin{vmatrix} & q_{\epsilon\epsilon} & q_{a\epsilon} & q_{\epsilon b} & q_{ab} \\ a & q_{a\epsilon} & q_{\epsilon\epsilon} & q_{ab} & q_{\epsilon b} \\ b & q_{\epsilon b} & q_{ab} & q_{\epsilon\epsilon} & q_{a\epsilon} \\ \end{vmatrix}$$

Answer 2

I ended up figuring it out, thanks all for the help.