2
$\begingroup$

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?

$\endgroup$
3
  • 1
    $\begingroup$ Define transition function properly. $\delta(q_2,a) = ?$ $\endgroup$
    – Complexity
    Commented Feb 3, 2018 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
    Commented Feb 3, 2018 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
    Commented Feb 3, 2018 at 9:30

1 Answer 1

3
$\begingroup$

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).

$\endgroup$
2
  • $\begingroup$ can u please show me a good reference $\endgroup$
    – venkat
    Commented Feb 5, 2018 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$ Commented Feb 6, 2018 at 6:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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