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.

enter image description here

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?

  • $\begingroup$ Why do you think so? Have to tried proving your claim or disproving the given answer? $\endgroup$ – Raphael Aug 24 '14 at 16:42

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.

  • $\begingroup$ Dear Jan, i think the input symbol x is in the alphabet? would u please add more detail? x/x/R ? $\endgroup$ – Mina Simin Aug 23 '14 at 6:31
  • $\begingroup$ @MinaSimin I added some explanation. What your professor wrote seems OK to me: $a,b$ as input symbols and $a,b,x$ as tape symbols. Also $\Delta$ probably is a tape symbol, but $\Delta$ is in some texts handled a little separately, so I cannot tell in your case. $\endgroup$ – Hendrik Jan Aug 23 '14 at 10:58
  • $\begingroup$ Thanks @Jan, so if x be in the alphabet the diagram not differ. am i right? $\endgroup$ – Mina Simin Aug 23 '14 at 11:01
  • $\begingroup$ @MinaSimin Yes, you are right. Symbol $x$ can also be in the input alphabet, and we obtain your language. $\endgroup$ – Hendrik Jan Aug 23 '14 at 11:03

You are right in that the machine verifies that the input word contains as many $a$ as $b$.

If $x$ is an allowed input symbol or not depends on the definition of the input alphabet, which can not be deduced from the image.

  • $\begingroup$ Dear FrankW, so if we say x is not in the alphabet (deduce from image) is wrong sentence? $\endgroup$ – Mina Simin Aug 22 '14 at 10:53
  • $\begingroup$ @MinaSimin Remember that we distinguish between input alphabet and tape alphabet. We can determine the tape alphabet from the image, but not the input alphabet. $\endgroup$ – FrankW Aug 22 '14 at 11:05
  • $\begingroup$ thanks so much Frankw. i conclude that just by trace number of a and b we can deduce number of a,b must be equal. and from this tips that x is not in the alphabet we couldent say anythings, except it's mentioned. thanks $\endgroup$ – Mina Simin Aug 22 '14 at 11:08

Not the answer you're looking for? Browse other questions tagged or ask your own question.