Consider the following problems : (i) Whether a finite state automaton halts…
2018
Consider the following problems :
(i) Whether a finite state automaton halts on all inputs?
(ii) Whether a given context free language is regular?
(iii) Whether a Turing machine computes the product of two numbers?
Which one of the following is correct?
- A.
Only (i) and (iii) are undecidable problems
- B.
Only (ii) and (iii) are undecidable problems
- C.
Only (i) and (ii) are undecidable problems
- D.
(i), (ii) and (iii) are undecidable problems
Attempted by 63 students.
Show answer & explanation
Correct answer: B
Final conclusion: Only the Turing-machine product problem (iii) is undecidable; the other two are decidable.
Problem (i): Whether a finite state automaton halts on all inputs?
Reason: Deterministic and nondeterministic finite automata process a finite input with a finite control and always terminate after reading the input. Therefore the question is decidable (trivially: every finite automaton halts on all finite inputs).
Problem (ii): Whether a given context-free language is regular?
Reason: This is a known decidable problem in formal-language theory. There are algorithmic methods (described in standard texts) to determine whether the language generated by a context-free grammar is regular, so the property is decidable.
Problem (iii): Whether a Turing machine computes the product of two numbers?
Reason: This asks whether the partial function computed by a given Turing machine equals the multiplication function. By Rice's theorem (or by standard reductions), any nontrivial semantic property of the function computed by a Turing machine is undecidable. Hence this problem is undecidable.
Overall: Only (iii) is undecidable. Therefore none of the provided choices correctly states the decidability classification.
A video solution is available for this question — log in and enroll to watch it.