GATE 2025 CS2 Q.24: solution and answer

Official answer: ASource: Official answer key, GATE 2025 CS2 (IIT Roorkee)

1. A deterministic pushdown automaton (DPDA) accepts exactly the deterministic context-free languages (DCFLs). The question asks which option holds for every language in the class it names, so we test each class against the DCFLs.

2. (A) Any DFA is a DPDA that never touches its stack, so every regular language is accepted by a DPDA. This option is true for any regular language.

3. (B) The language $\{w{w}^R\mid w\in \{a,b{\}}^{\ast }\}$ is context-free, but a machine must guess where the middle of the input is, and a DPDA cannot do that. No DPDA accepts it, so not every context-free language is accepted by a DPDA.

4. (C) A language accepted by a non-deterministic pushdown automaton is exactly a context-free language. The same language $w{w}^R$ is accepted by an NPDA but by no DPDA, so (C) fails.

5. (D) The language $\{a^n{b}^n{c}^n\mid n\ge 0\}$ is decidable but not context-free. No PDA of either kind accepts it, so a decidable language need not be accepted by a DPDA, and (D) fails.

6. The classes nest as regular $\subset$ DCFL $\subset$ CFL $\subset$ decidable. Only the regular languages are all inside the DCFLs, so the answer is (A).