World's most popular travel blog for travel bloggers.

# [Solved]: Strange TM Language on Definition

, ,
Problem Detail:

i prepare for Autotmata Course Final Exam.

in one of lecture, our professor draw this Turing Machine, and wrote DELTA is Neutral element of TM. it'w wrote:

Language of this TM is: {$W \in (a+b)^* : w=w^R$}

but i think x is in alphabet and the language is {$W \in (a+b+x)^* : n_a(w)=n_b(w)$}

$n_a$ is number of a's in w.

anyone could add some detail or hint for this note and which of them is correct?

#### Answered By : Hendrik Jan

Look at the instructions like $a/x,R$ in the diagram. They are used to "mark" the letters that have been compared (for every $a$ marked, we also mark a $b$). The TM repeatedly marks a pair of different symbols, and then restarts at the left side of the tape.

The machine works as follows. It starts at the leftmost symbol of a tape. It skips all $x$'s (in $q0$ moving right) and looks for the first $a$ or $b$, moving to $q1$ and $q2$ respectively (to distinguish cases). In that state it looks for the other symbol skipping $x$'s, and $a$'s or $b$'s depending on the letter we found first. At that point (in $q3$) it returns to the left of the tape (moving left until a blank $\Delta$ is found) and repeats. Acceptance if in $q0$ we only find $x$'s and reach the blank $\Delta$ to the right of the tape.

This indicates that $x$ is a special symbol from the tape alphabet, but not the input alphabet, and is used for administration during the computation. The original language is correct: $\{ w\in \{a,b\}^* \mid n_a(x) = n_b(x) \}$.

Technically it could be the case that $x$ is also in the input alphabet. However what your professor stated is consistent with the diagram. A language over $\{a,b\}$, and an extra tape symbol $x$ to mark symbols that have been accounted for.