Question

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?

• A. \(L = \{\langle M \rangle \mid M \text{ is a DFA such that } L(M) = \emptyset\}\)
• B. \(L = \{\langle M \rangle \mid M \text{ is a DFA such that } L(M) = \Sigma^*\}\)
• C. \(L = \{\langle M \rangle \mid M \text{ is a PDA such that } L(M) = \emptyset\}\)
• D. \(L = \{\langle M \rangle \mid M \text{ is a PDA such that } L(M) = \Sigma^*\}\)

Hint:

For PDAs, emptiness is decidable but universality is undecidable—this contrasts sharply with DFAs.

Answer 1

The Correct Option is D

Step 1: Problems related to DFAs.
For deterministic finite automata (DFAs), both the emptiness problem and the universality problem are decidable.

Hence, the languages described in options (A) and (B) are recursive.

---

Step 2: Emptiness problem for PDAs.
The emptiness problem for context-free languages (accepted by pushdown automata) is known to be decidable.

Therefore, the language described in option (C) is also recursive.

---

Step 3: Universality problem for PDAs.
The universality problem for PDAs—determining whether a PDA accepts Σ^*—is undecidable.

Hence, the corresponding language is not recursive.

---

Final Conclusion:
Among the given options, only (D) describes a non-recursive language.

Final Answer: (D)