Let 𝐿1 and 𝐿2 be two languages over a finite alphabet, such that 𝐿1∩𝐿2 and…

2026

Let 𝐿1 and 𝐿2 be two languages over a finite alphabet, such that 𝐿1∩𝐿2 and 𝐿2 are regular languages. Which of the following statements is/are always true?

  1. A.

    L1 is regular

  2. B.

    L1∪𝐿2 is regular

  3. C.

    L2' is context-free

  4. D.

    L1 is context-free

Attempted by 17 students.

Show answer & explanation

Correct answer: C

Given that L₂ is a regular language and the intersection L₁ ∩ L₂ is also regular.

Since every regular language is a context-free language, the intersection L₁ ∩ L₂ must be context-free. Therefore, the statement asserting that L₁ ∩ L₂ is context-free (Option C) is always true.

To verify why other options are not always true, consider the counter-example where L₂ = ∅ (the empty set). The empty set is regular. In this case, L₁ ∩ L₂ = ∅, which satisfies the condition regardless of what L₁ is. This means L₁ does not have to be regular or context-free, disproving options claiming constraints on L₁. Similarly, the union L₁ ∪ L₂ = L₁ in this case, so it is not necessarily regular.

Explore the full course: Gate Guidance By Sanchit Sir