The GATE Grind

GATE 2021 CS (CS2) – Question 22

Theory of Computation · Context-Free Grammars and Pushdown Automata · 1 mark · Multiple select

L1 is regular and L2 is context-free. Which are necessarily context-free?

  1. $L_1\cap\overline{L_2}$
  2. $\overline{\overline{L_1}\cup\overline{L_2}}$
  3. $L_1\cup(L_2\cup\overline{L_2})$
  4. $(L_1\cap L_2)\cup(\overline{L_1}\cap L_2)$

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (B) $\overline{\overline{L_1}\cup\overline{L_2}}$; (C) $L_1\cup(L_2\cup\overline{L_2})$; (D) $(L_1\cap L_2)\cup(\overline{L_1}\cap L_2)$

Explanation

B equals L1∩L2 by De Morgan, context-free because intersection with a regular language preserves context-freeness. C equals the universal language, regular. D simplifies to L2. A need not be context-free because context-free languages are not closed under complement; take L1 universal. Thus B,C,D.

More Context-Free Grammars and Pushdown Automata questions

All Context-Free Grammars and Pushdown Automata questions →