Theory of Computation (Automata)
What does Decidability refer to?
- A. A property of a problem indicating whether an algorithm can be constructed that always provides a correct yes/no answer. ✓
- B. A classification of formal grammars into four types based on their generative power.
- C. A sequence of characters that defines a search pattern, corresponding to regular languages.
- D. An abstract machine with a finite number of states used to recognize patterns in input strings.
Correct answer
A. A property of a problem indicating whether an algorithm can be constructed that always provides a correct yes/no answer.
Explanation
Decidability refers to a property of a problem indicating whether an algorithm can be constructed that always provides a correct yes/no answer.