Which of the following statements is not correct ?
2017
Which of the following statements is not correct ?
- A.
Every recursive language is recursively enumerable.
- B.
L = {0n 1 n 0n ? n=1, 2 , 3, ....} is recursively enumerable.
- C.
Recursive languages are closed under intersection.
- D.
Recursive languages are not closed under intersection.
Attempted by 61 students.
Show answer & explanation
Correct answer: D
Answer: The statement claiming that recursive languages are not closed under intersection is not correct.
Every recursive language is recursively enumerable: A decider halts on every input. Modify the decider to accept when it would accept and to loop on inputs it would reject; this yields a recognizer, so recursive implies recursively enumerable.
The language L = {0^n 1^n 0^n | n = 1,2,3,...} is recursively enumerable (indeed recursive): A Turing machine can first check the input has the form 0^+1^+0^+ and then repeatedly mark one symbol from each of the three blocks to verify equal counts. This procedure halts and decides membership.
Recursive languages are closed under intersection: Given deciders for two recursive languages, construct a decider that runs both deciders on the input and accepts exactly when both accept. Since each sub-decider always halts, the combined machine always halts, so the intersection is recursive.
Conclusion: The only incorrect statement among the choices is the one asserting that recursive languages are not closed under intersection; recursive languages are closed under intersection, so that claim is false.
A video solution is available for this question — log in and enroll to watch it.