Below are the excerpts from the automata text by Peter Linz.

Definition 9.3

Let $M = (Q,\Sigma,\Gamma,\delta,q_0,\square,F)$ be a Turing machine. Then the language accepted by $M$ is

$$L(M) = \{ w \in \Sigma^+ : q_0w \vdash ^* x_1q_fx_2 \text{ for some } q_f \in F,x_1,x_2 \in \Gamma^*\}$$

From the above definition it is clear that the $\Sigma^+$ in it does not allow the empty string to be accepted by the Turing machine.

Later in the example:

Example 9.6

For $\Sigma = \{0,1\}$, design a Turing machine that accepts the language denoted by the regular expression $00^*$.

Solution : Solution

Though the diagram is not given, I give it to simplify the situation. Then Linz adds,

Note that the Turing machine also halts in a final state if started in state $q_0$ on a blank. We could interpret this as acceptance of $\lambda$ (empty string), but for technical reasons the empty string is not included in Definition 9.3.

I have read the automata text by Ullman, but there was no such restrictions imposed on Turing machines. Using the concepts I have learnt from Ullman text, I could solve the problem as:

My solution

this no longer has the problem of acceptance of $\lambda$.

So what might be the technical reason or it is just a discretion of the author or reduction of the number of states?

  • 3
    $\begingroup$ There is no real reason that prevents a Turing machine from accepting the empty word. I suspect that "technical reason" is used in the sense of "technical convenience", i.e., some later proof or discussion in the book becomes easier/less tedious to argue about if there is no need to handle the empty word. Since I haven't read that book I can't say with certainty that this is what's going on, nor point you to a proof/argument where this technical simplification is used. $\endgroup$ – Steven Apr 4 at 17:12
  • $\begingroup$ @Steven I see. Ok. $\endgroup$ – Abhishek Ghosh Apr 4 at 17:42
  • $\begingroup$ Their own exercise 7g doesn't agree with their definition unless they expect the answer to be that no such machine exists. $\endgroup$ – plop Apr 4 at 17:48
  • $\begingroup$ @plop 7g ? I do not get it... $\endgroup$ – Abhishek Ghosh Apr 4 at 18:45

Your Answer

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

Browse other questions tagged or ask your own question.