Consider the following decision problems: (P₁) Does a given finite state machine accept a given string (P₂) Does a given context free grammar generate an infinite number of stings Which of the following statements is true? A)Both (P₁) and (P₂) are decidable B)Neither (P₁) nor (P₂) are decidable C)Only (P₁) is decidable D)Only (P₂) is decidable

Question

Quizplus · Accepted Answer

(P₁) is decidable because we can simulate the finite state machine on the given string to determine acceptance. (P₂) is also decidable because there are algorithms to determine if a context-free grammar generates an infinite number of strings by checking for recursive production rules.

Consider the Following Decision Problems