Which statements about L1 and L2 are necessarily true in GATE CS 2015 Set-1 Q14?

Statements I and IV are necessarily true. I: L1 is CFL → L1 is recursive → L1'' is recursive (recursive languages closed under complement). IV: L1'' is recursive (hence RE), L2 is RE, and RE is closed under union, so L1''∪L2 is RE. Statement II is false because if L2'' were recursive it would imply L2 is recursive — contradiction. Statement III is false because CFLs are not closed under complement.

Why is the complement of a CFL always recursive in GATE CS 2015 Set-1 Q14?

Every context-free language is recursive (decidable). Recursive languages are closed under complement — if a language is recursive, its complement is also recursive. Since L1 is CFL → L1 is recursive → L1'' is recursive. Note that L1'' need not be CFL (CFLs are not closed under complement) but it is always recursive.

Why is the complement of an RE non-recursive language not recursive in GATE CS 2015 Set-1 Q14?

A language is recursive if and only if both it and its complement are recursively enumerable. L2 is RE but not recursive, so L2''s complement cannot be RE (otherwise L2 would be recursive). Since L2'' is not even RE, it cannot be recursive. If L2'' were recursive it would be RE, making both L2 and L2'' RE, which would mean L2 is recursive — contradicting the given.

CFL Complement Recursive RE Language Properties Statements | GATE CS 2015 Set-1 Q14

Computer Sciences > Gate 2015 Set-1 > CFG

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

I. L₁' (complement of L₁) is recursive
II. L₂' (complement of L₂) is recursive
III. L₁' is context-free
IV. L₁' ∪ L₂ is recursively enumerable

I only

III only

III and IV only

I and IV only

Correct : CFG

L1 is context-free and L2 is recursively enumerable but not recursive.
Statement I — True: Every CFL is recursive, and recursive languages are closed under complement. Since L1 is CFL → L1 is recursive → L1'' is recursive.
Statement II — False: L2 is RE but not recursive. If L2'' were recursive, it would also be RE, and having both L2 and L2'' be RE would imply L2 is recursive — a contradiction. So L2'' is not recursive.
Statement III — False: CFLs are not closed under complementation. The complement of a CFL need not be context-free. For example, the complement of {aⁿbⁿcⁿ : n≥1} is CFL but not all CFL complements are CFLs. So L1'' is not necessarily context-free.
Statement IV — True: From I, L1'' is recursive, so L1'' is also RE. L2 is RE. RE languages are closed under union. Therefore L1'' ∪ L2 is RE.
Correct answer: D — I and IV only. Your page''s answer display is a bug showing "CFG" instead of D ✓

Similar Questions

Related Topics

Similar Questions

Related Topics

Question Options

Sign in to ExamPrev