# How to design a turing machine that recognizes any language?

here I have a problem. Design a turing machine that recognizes the language of all strings of even length over alphabet {a, b}.

soln:

Let turing machine is

$Tm =(Q, \Sigma, \Gamma, \delta, q_0 , h)$
$\Sigma=\{a, b \}$
$\Gamma=\{ a, b ,\# \}$
$Q = \{q_0, q_1, h\}$

after this I am confused in drawing partial function table. and please explain about the moves from 1 state to another.

## 1 Answer

You can actually do this without much power. A FSM would really be sufficient. You start at state $q_{0}$ and transition to $q_{1}$ when you read in your first non-blank character. When you read in the next non-blank character, transition back to $q_{0}$. So in this way, you are tracking even length or odd length. At $q_{0}$ transition to $h$ once you read the last character of the string. I.e., the string would be terminated by a $\#$, so $\#$ should cause a transition to $h$ when at $q_{0}$, and reject otherwise.

Edit: Really, you just keep moving left. So: $\delta(q_{0}, a) = \delta(q_{0}, b) = (q_{1}, L)$. That is, at $q_{0}$, move the tape head to the left and transition to $q_{1}$. $\delta(q_{0}, \#) = h$. That is, if you read in a blank character, move to the halt state.

Then you have $\delta(q_{1}, a) = \delta(q_{1}, b) = (q_{0}, L)$. Again, move the tape head one cell to the left and go to $q_{0}$ if you are at $q_{1}$ currently.

You can draw all of this in a table (I don't think I'd be able to get a great table going here), but hopefully this clarifies.

There is no need to go backwards on the tape cell, so the tape head never moves to the right. Again, the TM is really just simulating an FSM. This language is regular.

• I actually want to know how to show left , right move in a table ! I can draw transition diagram from it. – Bishwas Dec 15 '14 at 6:10
• I actually want to know how to show left , right move in a table ! I can draw transition diagram from it. according to text book here it is a solution states a b # q0 (q1, a, L ) ( q1, b, L ) ( h, #, N) q1 (q0, a, L ) ( q0, b, L ) * h * * accept where * is for undefined move. If u make me clear about this table then I will be fully satisfiied. And please explain how L and why not R ? – Bishwas Dec 15 '14 at 6:18
• I added more about the transition function. I think this should clarify. – ml0105 Dec 15 '14 at 6:22
• yes now I am clear.. and THANK YOU .. – Bishwas Dec 15 '14 at 6:28
• Glad I could help! :-) – ml0105 Dec 15 '14 at 6:32