Let \(⟨M⟩\) denote an encoding of an automaton \(M\). Suppose that Σ={0,1}.…
2021
Let \(⟨M⟩\) denote an encoding of an automaton \(M\). Suppose that Σ={0,1}. Which of the following languages is/are NOT recursive?
- A.
\(L = \{⟨M⟩\)\(∣ M\)\(is \ a \ DFA \ such \ that\)\( L(M)=∅\}\) - B.
\(L = \{{⟨M⟩ ∣ M \ is\ a\ DFA\ such\ that \ L(M)=Σ^*}\}\) - C.
\(L = \{{⟨M⟩ ∣ M\ is\ a\ PDA\ such\ that\ L(M)=∅}\}\) - D.
\(L = \{{⟨M⟩ ∣ M\ is\ a\ PDA\ such\ that\ L(M)=Σ^*}\}\)
Attempted by 62 students.
Show answer & explanation
Correct answer: D
Answer: The only language that is not recursive is the set of encodings of pushdown automata whose language equals Σ*.
Encodings of DFAs whose language is empty: Decidable. Use graph reachability from the start state; if no accepting state is reachable the DFA accepts no strings.
Encodings of DFAs whose language is Σ*: Decidable. Complement the DFA (swap accepting and non-accepting states) and test emptiness of the complement.
Encodings of PDAs whose language is empty: Decidable. Emptiness for pushdown automata (or equivalent context-free grammars) can be decided by checking which nonterminals derive terminal strings.
Encodings of PDAs whose language is Σ*: Undecidable. Universality for context-free languages is not decidable, so there is no algorithm that always determines whether a PDA accepts every string over Σ. Therefore this language is not recursive.
Conclusion: exactly the set of encodings of pushdown automata whose language equals Σ* is not recursive.
A video solution is available for this question — log in and enroll to watch it.