theory of computation

Question

can a turing machine accept $\varepsilon$ ??? please explain ??? 

this question says it can accept ...https://gateoverflow.in/941/gate2003-53

Answer 1

From your question I can say that you are following some coaching material. Epsilon means empty string. $L = \{\epsilon\}$ is a language which has empty string in it (here no other strings) and we can draw a DFA for this making it a regular language. A regular language is by hierarchy a CFL, CSL, Recursive and also a recursively enumerable language. This also means epsilon is accepted by a PDA, LBA and also a Turing machine. How a TM accept an empty string is a better question.

Comments

@Arjun sir,  LBA has not been mentioned in many books, we know that LBA is a machine which implements CSL. And LBA has 2 stacks. We also know that FA + 2 Stacks is as powerful as Turing Machine. This makes LBA and TM similar.

I had read in a booklet that the only difference in CSL and REAL is that CSL can not have empty string, while REL can have. This makes every CSL, REL but Every REL is not CSL , which seems correct. But. I don't know it for sure. Please put some light.

---

@Rude No. That is not correct. As you told we need not worry about how an LBA works as it is not given in most books. And it does implement a CSL. The difference between a CSL and Recursive language is not the absence of empty string. The classical definition of CSL does not include empty string but it is added as a special condition or else Chomsky hierarchy fails. But LBA does not have any issue in accepting empty string.

The difference between a CSL and recursive language is that a TM can have infinite tape length. But an LBA should accept any string within $kn$ tape length where $n$ is the input length and $k$ is some constant. So, for empty string this condition fails and that is why it requires a special rule.

---

@Arjun Sir , Based on above discussion what should be clear cut answer of this Question -  How a TM accept an empty string???