Which one of the following problems is decidable for recursive languages…
2018
Which one of the following problems is decidable for recursive languages \((𝐿)\) ?
- A.
Is
\(𝐿=𝜙\)? - B.
Is
\(𝑤∈𝐿\), where 𝑤 is a string ? - C.
Is
\(𝐿=Σ^∗\)? - D.
Is
\(𝐿=𝑅\), where\(𝑅\)is a given regular set ?
Attempted by 62 students.
Show answer & explanation
Correct answer: B
Key idea: a recursive (decidable) language has a total algorithm that halts on every input and correctly decides membership.
Decidable problem: To determine whether a given string w is in the language, run the decider for the language on w. Because the decider always halts, this procedure always returns accept or reject, so membership is decidable.
Undecidable problems: Emptiness (whether the language is empty), universality (whether the language equals all strings), and equality with a given regular set are nontrivial semantic properties of the language. By Rice-style results (or standard reductions from the halting problem), there is no general algorithm that decides these properties for an arbitrary description of a decidable language.
Relation between emptiness and universality: universality is equivalent to emptiness of the complement. Since emptiness is undecidable in general, universality is undecidable as well.
Conclusion: The only problem among those listed that is always decidable for a recursive language is the membership question: given a string w, decide whether w ∈ L.
A video solution is available for this question — log in and enroll to watch it.