Redirected
6,581 views
11 votes
11 votes
Does turing machine accepts epsilon?

2 Answers

Best answer
37 votes
37 votes

Suppose the answer is "no"

  1. Decidability of whether a TM accepts empty string becomes trivial - but this is an undecidable problem
  2. Set of all recursively enumerable language will never be a superset of set of all context-sensitive languages or context-free languages or not even regular languages as all these can include empty string.

So the answer is "yes". A TM accepts empty string when it can go to an accept state on "B" (blank symbol) on input tape or if the initial state is an accepting state (similar to finite automata).

edited by
3 votes
3 votes
Turing Machine can accept Epsilon? No

Because when we telling turing machine accept epsilon, that means yes cases of TM is accepts nothing.

Means u can simply ask this question "Is TM accepts nothing?"

We can only check that if TM accepts a finite or infinite language . But how can we say if there is nothing as a string, then still TM accepts it. It can never be decided. So, TM accepts epsilon is undecidable or not even Recursive Enumerable.

Related questions

3 votes
3 votes
2 answers
2
3 votes
3 votes
1 answer
3
3 votes
3 votes
2 answers
4