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?
- A.
L1 is regular
- B.
L1∪𝐿2 is regular
- C.
L2' is context-free
- 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.