Which of the following problems are decidable? 1) Does a given program ever…
2012
Which of the following problems are decidable?
1) Does a given program ever produce an output?
2) If \(L\) is a context-free language, then, is \(\overline L\) also context-free?
3) If \(L\) is a regular language, then, is \(\overline L\) also regular?
4) If \(L\) is a recursive language, then, is \(\overline L\) also recursive?
- A.
1, 2, 3, 4
- B.
1, 2
- C.
2, 3, 4
- D.
3, 4
Attempted by 60 students.
Show answer & explanation
Correct answer: D
Answer: statements 3 and 4 are decidable.
Regular languages: decidable. Regular languages are closed under complement. Given a regular description (DFA/NFA/regex), convert it to a DFA and flip accepting and non-accepting states to obtain a DFA for the complement, so the complement is guaranteed regular.
Recursive languages: decidable. If a language is recursive (there is a decider that halts on every input), then running that decider and inverting accept/reject yields a decider for the complement, so the complement is recursive.
A video solution is available for this question — log in and enroll to watch it.