Which of the following statements is not correct ?

2017

Which of the following statements is not correct ?

  1. A.

    Every recursive language is recursively enumerable.

  2. B.

    L = {0n 1 n 0n ? n=1, 2 , 3, ....} is recursively enumerable.

  3. C.

    Recursive languages are closed under intersection.

  4. 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.

Explore the full course: Mppsc Assistant Professor