Project ForgeSign up free
Theory of Computation
Grammars, Turing Machines & Decidability
GATE 2017
Hard

Let L1, L2 be any two context-free languages and R be any regular language. Then which of the following is/are CORRECT?

I. L1 ∪ L2 is context-free.
II. complement(L1) is context-free.
III. L1 − R is context-free.
IV. L1 ∩ L2 is context-free.
  • AI, II and IV only
  • I and III only
  • CII and IV only
  • DI only

Explanation

CFLs ARE closed under union (I true) and under intersection with a regular language, which is exactly what set difference with a regular set amounts to: L1 − R = L1 ∩ complement(R), and complement(R) is still regular since regular languages are closed under complement, so this is CFL ∩ regular = CFL (III true). CFLs are NOT closed under complement in general (II false) or under intersection with another CFL (IV false). So only I and III hold.

Source: GATE CS 2017 (Session 2) (2017)

This question is part of a 15-day revision cycle — sign in and Project Forge will bring it back the day before you'd forget it.

Start revising free