777 views
0 votes
0 votes

1 Answer

0 votes
0 votes
a)1. Run the TM on the string
w. If it ever enters its accept state, accept.
2. If it ever enters its reject, reject.

3) it can also go in infinite loop

Thus, we've proven that it is undecidable.

b)

Decidability is possible if the property is there for any recursively enumerable languages or if it is absent for all recursively enumerable languages (trivial)

since a given TM has a language which is REL

So TM accepts a REL is trivial property so it is decidable

No related questions found