GATE CSE 2021 Set 2 Q22: Closure: regular L1 and context-free L2 combinations

Let $L_1$ be a regular language and $L_2$ be a context-free language. Which of the following languages is/are context-free?

Try it: multiple select: one or more correct options

Select all correct options. No negative marking, no partial marks.

Show answer and explanation

Answer: B, C, D (official GATE 2021 final answer key)

Concept used: CFLs are closed under intersection with a regular language and under union, but not under complement.

First step: Simplify each with set algebra: (B) is $L_1 \cap L_2$ by De Morgan, (C) is $\Sigma^*$ , (D) is $L_2$ ; (A) needs $\overline{L_2}$ .

Full step-by-step solution

Detailed working, common mistakes and linked mock tests will be available with a free GATEiit account. Log-in is coming soon.

Share this question

Source: official GATE 2021 Set 2 CS question paper and final answer key, organised by IIT Bombay. Question paper · Answer key