4
$\begingroup$

The following is an excerpt from the book "An Introduction to Formal Languages and Automata" by Peter Linz.

Definition of Turing Machine

My question is, why is $\Sigma^+$ used and not $\Sigma^\ast$?

$\endgroup$
6
$\begingroup$

Immediately after the definition, the text (fifth edition) continues

This definition indicates that the input $w$ is written on the tape with blanks on either side. The reason for excluding blanks from the input now becomes clear: It assures us that all the input is restricted to a well-defined region of the tape, bracketed by blanks on the right and left. Without this convention, the machine could not limit the region in which it must look for the input; no matter how many blanks it saw, it could never be sure that there was not some nonblank input somewhere else on the tape.

This differs from the approach some other authors take, using a tape that's bounded on the left and unbounded in the other direction, and stipulating that the input string begins at the leftmost cell and continues to the first blank. I don't find Linz's definition to be better, if for no other reason than it eliminates any language containing the empty string from being the language of a TM.

$\endgroup$
  • $\begingroup$ Actually he has mentioned in the book that "but for technical reasons the empty string is not included in Definition", but he didn't explain the actual reasons. $\endgroup$ – Manu Thakur Sep 6 '17 at 13:59
  • $\begingroup$ @ManuThakur, you may be reading an earlier edition. The definition stumped me at first, so I'm sure you're not be the first student to find that confusing. Good thing the author revised it! $\endgroup$ – ymbirtt Sep 6 '17 at 20:16
  • $\begingroup$ @ymbirtt I am reading fourth edition. author revised it in which edition? $\endgroup$ – Manu Thakur Sep 7 '17 at 4:15
  • $\begingroup$ @ManuThakur, the answer we're both commenting on says that it was revised in the fifth edition. $\endgroup$ – ymbirtt Sep 7 '17 at 7:25
3
$\begingroup$

I cannot tell you whether this is a mistake, but I can tell you what you should do in such cases.

  1. Double check that the author is using the same notation that you are using. In this case, find in the textbook the definition of $\Sigma^{+}$.

  2. Assuming there is no confusion about the notation, read surrounding text to see if there is a comment as to why he is excluding the empty word.

  3. Assuming there is no confusion about the notation and no comment, look through the text to see if the author is following his own definition, or is violating it. Does he ever consider a language that contains the empty word? When he defined what a language is, is the empty word allowed?

  4. Check other sources to see whether other authors allow the empty word to be part of a language. (I can tell you that they mostly do.)

  5. Assuming that the author allows the empty word when he defined what a language is, and does indeed consider such languages, then you may safely conclude that you are looking at a typo and it should have been $\Sigma^{*}$.

  6. Optional: respectfully write an email to the author and ask him, but only after you have made the effort to resolve the issue yourself.

$\endgroup$
  • $\begingroup$ Actually he has mentioned that "but for technical reasons the empty string is not included in Definition", but he didn't explain the actual reasons. $\endgroup$ – Manu Thakur Sep 6 '17 at 13:58
  • $\begingroup$ Well then, that solves this question. Are you going to ask about the reasons or try to figure them out? Look at how he defines Turing machines and see what goes wrong with accepting the empty word. $\endgroup$ – Andrej Bauer Sep 6 '17 at 14:31
  • $\begingroup$ i will figure it out myself why epsilon is excluded. $\endgroup$ – Manu Thakur Sep 6 '17 at 14:39
  • 1
    $\begingroup$ Step 5a: check to see if the book has errata published anywhere (such as on the publisher's website) $\endgroup$ – Roger Lipscombe Sep 6 '17 at 15:22
1
$\begingroup$

This is a question for the author, Peter Linz. Some authors include the empty word as a possible member of the language of a Turing machine. It is possible that the machine will always get "stuck" if it starts at the configuration $q_0$, but it is hard to tell without knowing the exact definitions in the textbook.

$\endgroup$
  • $\begingroup$ Actually he has mentioned that "but for technical reasons the empty string is not included in Definition", but he didn't explain the actual reasons. $\endgroup$ – Manu Thakur Sep 6 '17 at 13:58

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.