# How to draw a Turing Machine for Even-Even

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!

• It seems that your language is regular. Nov 20, 2012 at 6:12
• I don't see where the problem is, your machine appears to work fine (the one in the diagram), although your description of the algorithm doesn't match the diagram (and as A.Schulz suggests, the language is regular). Nov 20, 2012 at 7:59
• Note that the usual assumption is that unused cells on the TM's tape contain some gap symbol like $\#$ or $\square$. Therefore, you can always recognise the end of your input without rewriting it.
– Raphael
Nov 20, 2012 at 9:27

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}$$

• Why don't we just encode the NFA's state in the TM's state?
– Raphael
Nov 26, 2012 at 0:49
• If that's permissible, than that would certainly be more elegant; constructing TMs for regular languages is not typical. Nov 26, 2012 at 3:04
• I don't see why it would not be permissable; 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 $\varepsilon$-transitions, and then you basically have your equivalent TM.
– Raphael
Nov 26, 2012 at 11:42
• One technical note regarding that: depending on how you define a deciding TM, you may have to write something after all (and maybe even delete the input); usually that would be $0$ or $1$, depending on whether you accept or not. This is an easy update to the "naive" translation. For common definitions, entering an accepting (or non-accepting) state will be enough "output" for a decider, so the "naive" translation works just fine.
– Raphael
Nov 26, 2012 at 18:04

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