recategorized by
1,754 views
1 votes
1 votes

Consider the following problems :

  1. Whether a finite state automaton halts on all inputs?
  2. Whether a given context free language is regular?
  3. Whether a Turing machine computes the product of two numbers?

Which one of the following is correct?

  1. Only i and iii are undecidable problems
  2. Only ii and iii are undecidable problems
  3. Only i and ii are undecidable problems
  4. i, ii and iii are undecidable problems
recategorized by

2 Answers

1 votes
1 votes
(I). Finite automaton accept all string which are in language and reject those strings which are not in language so it is decidable

(ii). CFL may or may not be regular so it undecidable

(iii). Behaviour of TM is not given so it is also undecidable

Hence 4. (ii) &(iii ) is undecidable
0 votes
0 votes
Answer is B.

Only the first one is a decidable problem.

Related questions

1 votes
1 votes
3 answers
1