consider the turing machine below

is the string aabb in the language of this Turing machine ?? as upon reading aa it goes to the final state but upon b there is no transition defined so won't it result in a dead configuration?

  • 1
    $\begingroup$ Define transition function properly. $\delta(q_2,a) = ?$ $\endgroup$ – Complexity Feb 3 '18 at 9:13
  • $\begingroup$ @Complexity the transition function is not given for q2 on a there is no move defined upon q2 for any input $\endgroup$ – venkat Feb 3 '18 at 9:17
  • $\begingroup$ in PDA with final state if final state is reached there can be inputs on the stack but in TM i dont think so but in wikipedia - " If δ is not defined on the current state and the current tape symbol, then the machine halts; is given in wiki so once on reaching the final state doesnt it consider the rest of the input ? $\endgroup$ – venkat Feb 3 '18 at 9:30

When a Turing machine enters an accepting state, it immediately stops running and accepts whatever the original input string was (regardless of the state of the tape). So given the input aabb, the Turing machine will read the two as and enter the accepting state $q_2$, at which point it will halt and accept aabb.

In this case it doesn't matter that there's no transition for reading a b from $q_2$ because we've already accepted (though you are correct in general that whenever we're running a Turing machine and we arrive at a state with no transition defined for the character we're reading, we implicitly go to a dead state and reject).

  • $\begingroup$ can u please show me a good reference $\endgroup$ – venkat Feb 5 '18 at 11:40
  • 1
    $\begingroup$ This is how accepting and rejecting are defined in "Introduction to Theory of Computation" by Michael Sipser. Specifically, "accepting and rejecting configurations are halting configurations and do not yield further configurations" [pg. 141, 2nd ed.]. $\endgroup$ – roctothorpe Feb 6 '18 at 6:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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