GATE CS 2021 Set 1 Q.22 (CS Q.12): Decidability, Reducibility and Undecidability

Let $\langle M \rangle$ denote an encoding of an automaton $M$ . Suppose that $\Sigma = \{0,1\}$ . Which of the following languages is/are NOT recursive?

$L = \{\langle M \rangle \mid M \text{ is a DFA such that } L(M) = \emptyset\}$

$L = \{\langle M \rangle \mid M \text{ is a DFA such that } L(M) = \Sigma^*\}$

$L = \{\langle M \rangle \mid M \text{ is a PDA such that } L(M) = \emptyset\}$

$L = \{\langle M \rangle \mid M \text{ is a PDA such that } L(M) = \Sigma^*\}$

Official answer and solution

Official answer: D
From: Official GATE 2021 answer key

Note on this question

Official key designates this question as MSQ with single correct option D.

Solution

Apply known decidability results for formal languages and automata.

Recall standard decidability results for DFAs and PDAs:

Option A: Emptiness for DFA ( $L(M) = \emptyset$ ) is decidable by graph reachability from the start state to any accept state. The language is recursive.
Option B: Universality for DFA ( $L(M) = \Sigma^*$ ) is decidable by complementing the DFA and testing for emptiness. The language is recursive.
Option C: Emptiness for PDA ( $L(M) = \emptyset$ ) is equivalent to CFG emptiness (checking if the start variable can derive a string of terminals), which is decidable in polynomial time. The language is recursive.
Option D: Universality for PDA / CFL ( $L(M) = \Sigma^*$ ) is a famous undecidable problem (proven by reduction from the Post Correspondence Problem or valid computation histories of Turing machines). Therefore, this language is NOT recursive.

Hence, only option D is not recursive.

Final answer

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2021 Computer Science and Information Technology (CS, Set-1)
Question: 22 of 65, printed as CS Q.12
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source