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: DFA-related problems.
For DFAs, both the emptiness problem and the universality problem are decidable. Hence, languages in options (A) and (B) are recursive.

Step 2: PDA emptiness problem.
The emptiness problem for context-free languages (accepted by PDAs) is decidable. Therefore, option (C) corresponds to a recursive language.

Step 3: PDA universality problem.
The universality problem for PDAs (checking whether a PDA accepts \(\Sigma^*\)) is undecidable. Hence, the corresponding language is NOT recursive.

Step 4: Conclusion.
Only option (D) describes a non-recursive language.

Final Answer: (D)