GATE CS 2000 Q2.9 — Undecidability

To determine the decidability of the two decision problems, let us analyze them individually:

1. Problem $(P1)$: Does a given finite state machine accept a given string?

   This is the membership problem for regular languages. Given a finite state machine $M$ and a string $w$, we can simulate the execution of $M$ on $w$. Since $M$ has no loops without consuming input (or we can easily convert it to a deterministic finite automaton), the simulation is guaranteed to halt in exactly $|w|$ steps. If the final state is an accepting state, we accept; otherwise, we reject. Thus, $(P1)$ is decidable.

2. Problem $(P2)$: Does a given context-free grammar (CFG) generate an infinite number of strings?

   This is the finiteness problem for context-free languages. We can decide this using the following algorithm:

   • First, simplify the CFG by eliminating all useless symbols (non-generating and unreachable variables).
   • Construct a directed dependency graph where the vertices are the remaining non-terminals, and a directed edge exists from $A$ to $B$ if there is a production of the form $A \to \alpha B \beta$.
   • If this dependency graph contains a cycle, the grammar can generate infinitely long derivations, meaning the language is infinite. If there are no cycles, the language is finite.

   Since cycle detection in a finite graph is decidable, the finiteness problem for CFGs is decidable. Thus, $(P2)$ is decidable.

Since both $(P1)$ and $(P2)$ are decidable, the correct option is A.