GATE CS 2008 Q10 — Undecidability

To determine which of the problems are decidable, let us analyze each statement individually:

1. Whether the intersection of two regular languages is infinite:

   Regular languages are closed under intersection. If $L_1$ and $L_2$ are regular languages represented by DFAs, we can construct a product DFA representing $L_1 \cap L_2$. To check if this resulting regular language is infinite, we can check if the DFA contains a cycle that is reachable from the start state and can reach an accepting state. Since this graph reachability and cycle detection can be done in finite time, this problem is decidable.

2. Whether a given context-free language is regular:

   Testing whether a given Context-Free Language (CFL) is regular is a well-known undecidable problem. There is no algorithm that can determine if an arbitrary CFG generates a regular language.

3. Whether two push-down automata accept the same language:

   This is the equivalence problem for PDAs (or CFLs), i.e., determining if $L(M_1) = L(M_2)$. The equivalence problem for context-free languages is undecidable.

4. Whether a given grammar is context-free:

   A grammar $G = (V, \Sigma, R, S)$ is context-free if every production rule in $R$ is of the form $A \to \alpha$, where $A \in V$ and $\alpha \in (V \cup \Sigma)^*$. Since a grammar is defined by a finite set of rules, we can verify this syntactic condition for each rule in finite time. Thus, this is trivially decidable.

Therefore, only statements I and IV are decidable, which corresponds to option B.