[Math] turing machine accept and reject state

automatacomputer scienceturing-machines

I am pretty new to Turing Machines and I am trying to understand the basic things first…so my question is , would this machine accept all words ending in 'a' ? if that's the case would the REJECT state be all string without 'a' and ending with 'b' ?

enter image description here

Best Answer

This Turing-machine's head will move to right on encounter of every 'a' and whenever it find the 'b', this will change it to 'a' and move to left and halt.

(a,a,R) : says that if tape symbol is 'a' keep it 'a' only and move R(Right).

(b,a,L) : says that if tape symbol is 'b' make it 'a' and move L(left) with halt.

So, this TM will accept all string ending with 'b', as it moves to halt state if and only if 'b' comes.

I hope this will help. good luck :)

Related Question