Consider the following decision problems: (P1) Does a given finite-state…
GATE · 2000 · CS · Question 2 subparts
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?
- A.
Both (P1) and (P2) are decidable
- B.
Neither (P1) nor (P2) is decidable
- C.
Only (P1) is decidable
- D.
Only (P2) is decidable
Attempted by 103 students.
Sign up free to check your answer
Sign up freeLoading lesson…