Let \(L_1\) be a regular language and \(L_2\) be a context-free language.…
2021
Let \(L_1\) be a regular language and \(L_2\) be a context-free language. Which of the following languages is/are context-free?
- A.
\(L_1 \cap \overline{L_2} \\\) - 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)\)
Attempted by 66 students.
Show answer & explanation
Correct answer: B, C, D
Given that L1 is regular and L2 is context-free, simplify each expression and use closure properties to decide which are guaranteed to be context-free.
L1 ∩ complement(L2): Not necessarily context-free. The complement of a context-free language need not be context-free. If L1 = Σ*, this expression equals complement(L2), which may be non-context-free.
complement(complement(L1) ∪ complement(L2)): By De Morgan this equals L1 ∩ L2. Intersection of a regular language with a context-free language is always context-free, so this expression is context-free.
L1 ∪ (L2 ∪ complement(L2)): Since L2 ∪ complement(L2) = Σ*, the union is Σ*, which is regular (and therefore context-free). So this expression is context-free.
(L1 ∩ L2) ∪ (complement(L1) ∩ L2): Factor L2 to get (L1 ∪ complement(L1)) ∩ L2 = Σ* ∩ L2 = L2, which is context-free.
Conclusion: The guaranteed context-free languages are the simplified expressions equal to L1 ∩ L2, Σ*, and L2; the first expression L1 ∩ complement(L2) is not guaranteed to be context-free.
A video solution is available for this question — log in and enroll to watch it.