-
Consider the following decision problems:
P1. Does a given finite state machine accept a given string?
P2. Does a given context-free grammar generate an infinite number of strings?
Which of the following statements is true?
-
- Both P1 and P2 are decidable
- Neither P1 nor P2 are decidable
- Only P1 is decidable
- Only P2 is decidable
- Both P1 and P2 are decidable
Correct Option: A
In P1, A given finite state machine accepts a given string if it is decidable because in decidable problem there exists a turing machine that gives the correct answer for every statement in the domain of the problem. A class of problems with two outputs yes or no is said to be decidable (solvable), if there exist some definite algorithm which always terminates (halts) with one of the two outputs yes or no. Similarly, in P2 , the context-free grammar generates.
