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 language is recursive if there exists a halting Turing machine (decider) that decides membership in the language.

• (A) $L = \{\langle M \rangle \mid M \text{ is a DFA such that } L(M) = \emptyset\}$: Decidable/Recursive. The emptiness problem for DFAs ($E_{\text{DFA}}$) can be decided by graph reachability algorithms (BFS/DFS) to check if any accept state is reachable from the start state.

• **(B) $L = \{\langle M \rangle \mid M \text{ is a DFA such that } L(M) = \Sigma^*\}$:** Decidable/Recursive. Since DFAs are closed under complementation, we can construct $\overline{M}$ such that $L(\overline{M}) = \Sigma^* \setminus L(M)$ and then check if $L(\overline{M}) = \emptyset$.

• (C) $L = \{\langle M \rangle \mid M \text{ is a PDA such that } L(M) = \emptyset\}$: Decidable/Recursive. The emptiness problem for CFLs/PDAs ($E_{\text{CFG}}$) is decidable by checking whether the start variable can derive any terminal string.

• **(D) $L = \{\langle M \rangle \mid M \text{ is a PDA such that } L(M) = \Sigma^*\}$:** Undecidable (NOT recursive). The universality problem for context-free languages ($ALL_{\text{CFG}}$ / $ALL_{\text{PDA}}$) is undecidable via reduction from the Post Correspondence Problem (PCP) or by representing valid computation histories of a Turing machine.

Therefore, only D is NOT recursive.