0
$\begingroup$

In the image, the language of the TM is defined on (a, b, c, d) and there is no transition on final state, but strings consisting of d are also part of the language.

In all TM problems I have seen until now, all transitions not defined are considered to go to the rejecting state (qrej.).

So in this TM also any transition on {a, b, c or d} from the final state should go to rejecting state and L(M) should be the string {abc}. But the solution states that the machine accepts the regular language abc(a+b+c+d)*. enter image description here

According to me the answer should be options (a) and (c) but the answer is (a) and (d). Please explain how this acceptance of TM works and also how transition of final state are considered when it is not defined explicitly.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

When the Turing Machine enters an accepting state, it immediately halts and accepts. This is somewhat contrasting to many other automata that have to exhaust their input strings; the TM doesn't have to. Therefore the TM accepts all strings beginning with $abc$, while $G$ generates all strings beginning with $abc$ containing no $d$.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Thanks for answering. Could you please also provide a standard source that states the same for my reference? $\endgroup$
    –  nietzsche
    Nov 16, 2021 at 7:45
  • 1
    $\begingroup$ @nietzsche This is pretty universal so I just picked the first authoritative-looking Google hit. "A given Turing machine has a fixed, finite set of states. One of these states is designated as the start state. This is the state in which the Turing machine begins a computation. Another special state is the halt state. The Turing machine’s computation ends when it enters its halt state." eng.libretexts.org/Bookshelves/Computer_Science/… $\endgroup$
    – kviiri
    Nov 16, 2021 at 9:16
  • $\begingroup$ (Alternative versions are occasionally used, but they are basically re-dressings of the same idea: the Turing Machine halts when its state transition function instructs it to, regardless of whether it's consumed all – or even any! – of its input string) $\endgroup$
    – kviiri
    Nov 16, 2021 at 9:18
  • 1
    $\begingroup$ @nietzsche Actually you may define Turing Machines in a lot of different ways, which are all computationally equivalent. It is often proper to make your model explicit as much as needed. However, unless you use special markers on the input tape, it is not possible to make sure that the whole input has been read $\endgroup$
    – babou
    Nov 16, 2021 at 17:50

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.