Consider the following decision problems: (P1) Does a given finite-state…
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?
Answer: A. Both (P1) and (P2) are decidable — P1 is decidable because a finite-state machine can be simulated on the given finite input string. After reading the whole string, we can directly check…
- 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 27 students.
Show answer & explanation
Correct answer: A
P1 is decidable because a finite-state machine can be simulated on the given finite input string. After reading the whole string, we can directly check whether the reached state is accepting.
P2 is also decidable. For a context-free grammar, we can remove useless symbols and then check whether there is a reachable, productive cycle among nonterminals. Such a cycle lets the grammar pump and generate arbitrarily long strings, so the language is infinite; if no such cycle exists, only finitely many derivations are possible.
Therefore both P1 and P2 are decidable. Option A is correct.
Explore the full course: Iocl Engineers Officers Grade A Paper 2