GATE CS 1989 Q3-iii — Undecidability

To determine which of the problems are undecidable, let us analyze each option:

1. Membership problem in context-free languages: Given a context-free grammar $G$ and a string $w$, deciding whether $w \in L(G)$ is decidable. For example, the Cocke-Younger-Kasami (CYK) algorithm can solve this in $O(|w|^3)$ time.
2. Whether a given context-free language is regular: Given a context-free grammar $G$, determining whether there exists an equivalent regular language is undecidable. This is a standard undecidable property of CFLs shown via reduction from the Post Correspondence Problem (PCP) or Turing machine computation histories.
3. Whether a finite state automaton halts on all inputs: A finite state automaton (DFA/NFA) processes exactly one input symbol per step and has no mechanism to loop infinitely without consuming input. Thus, it always halts on any finite input string, making this problem trivially decidable.
4. Membership problem for type 0 languages: Type 0 languages are recursively enumerable (RE) languages, which are recognized by Turing machines. Deciding whether a string $w$ belongs to a type 0 language is equivalent to the Turing machine acceptance problem ($A_{TM}$), which is famously undecidable.

Thus, the undecidable problems are B and D.