Consider the following decision problems: (P1) Does a given finite-state…

PYQ GATE 2000

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?

  1. A.

    Both (P1) and (P2) are decidable

  2. B.

    Neither (P1) nor (P2) is decidable

  3. C.

    Only (P1) is decidable

  4. D.

    Only (P2) is decidable

Attempted by 153 students.

Sign up free to check your answer

Sign up free

Explore the full course: Zero To Hero

Loading lesson…