MCQ IN COMPUTER SCIENCE & ENGINEERING

Detailed explanation-1: -Context-free languages are not closed under complementation. L1 and L2 are CFL. Then, since CFLs closed under union, L1 ∪ L2 is CFL.

Detailed explanation-2: -Context-free languages are not closed under intersection or complement. This will be shown later. The intersection of a context-free language and a regular language is context-free (Theorem 3.5. 2).

Detailed explanation-3: -Context Free Grammar (CFG) is not closed under complementation, set difference and intersection. Context Free Grammar (CFG) is closed under union, concatenation, Kleen closure, Reversal, Product etc. Important Points: Deterministic Context Free Grammar (DCFG) is closed under complementation but not under union.

Detailed explanation-4: -The complement of a context-free language can be context-free or not; the complement of a non-context free language can be context-free or not. Every regular language is context-free. Regular languages are closed under complement, so the complement of a regular language is regular.

Detailed explanation-5: -Theorem: CFLs are not closed under complement If L1 is a CFL, then L1 may not be a CFL. They are closed under union. If they are closed under complement, then they are closed under intersection, which is false.