For any two languages \(L_1\) and \(L_2\) such that \(L_1\) is context-free…

GATE · 2015 · CS · Set 1 · Computer Science & IT

For any two languages L1L_1 and L2L_2 such that L1L_1 is context-free and L2L_2 is recursively enumerable but not recursive, which of the following is/are necessarily true?

I. L‾1\overline L_1 (complement of L1L_1) is recursive

II. L‾2\overline L_2 (complement of L2L_2) is recursive

III. L‾1\overline L_1 is context-free

IV. ​​L‾1∪L2​​\overline L_1 \cup L_2 is recursively enumerable

  1. A.

    I only

  2. B.

    III only

  3. C.

    III and IV only

  4. D.

    I and IV only

Attempted by 98 students.

Sign up free to check your answer

Sign up free

Explore the full course: Gate Guidance By Sanchit Sir

Loading lesson…