264 views
2 votes
2 votes

Why answer a is not correct and how C is answer?

1 Answer

Best answer
2 votes
2 votes

Lets consider each option one by one ..

a) The given problem is actually a well known problem known as state entry problem . And this problem is similar to halting problem which is know as an RE language problem . Hence state entry problem is also partially decidable problem and hence comes under undecidable problem.

b) This problem is a variant of the blank tape halting problem which is also an undecidable problem.

d) Whether the language accepted by M is finite : Now this is a language related property and hence we can check it using Rice's theorem. Now the membership problem i.e. given the string w as mentioned in the question and the TM may not halt when w is given as input . So the problem is finiteness i.e. whether the TM accepts finite number of strings is more harder than this as we have to check each string that is accepted by the TM. Hence it is an undecidable problem.

c) This is actually decidable . First of all this is a machine related property hence Rice theorem is not applicable . Hence in the process of reading the string 'w' , we can see whether the head is moving left or right using the transition functions of the given TM..Hence we can find solution to this problem and we have a method for this as we have transition function.Hence this problem is decidable.

Hence C) should be the correct option.

selected by

Related questions

0 votes
0 votes
1 answer
2
krmanish043 asked Dec 25, 2018
466 views
Which of the following is correct statement?DPDA and NPDA have the same powers.An NFA with 1 Stack is NOT equivalent to NPDA.DPDA with final state acceptance has the same...
0 votes
0 votes
0 answers
4
Kuldeep Pal asked Dec 3, 2017
261 views
Time complexity to find a string of length k is accepted by a given deterministic finite automata on n states, over 2 symbol input alphabet isA. O(k)B. O(nk)C. O(klogn)D....