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?

1. AOnly (i) and (iii) are undecidable problems
2. BOnly (ii) and (iii) are undecidable problems
3. COnly (i) and (ii) are undecidable problems
4. D(i), (ii) and (iii) are undecidable problems

Pick an option to check yourself, or open the answer below.

Show answer & explanation

Correct answer: B. Only (ii) and (iii) are undecidable problems

Explanation

A finite automaton always halts after reading its input, so (i) is trivially decidable. Whether a CFL is regular is undecidable, and whether a TM computes a given function is undecidable by Rice's theorem.