Consider \(𝑅\) to be any regular language and \(𝐿_1\), \(𝐿_2\) be any two…
2018
Consider \(𝑅\) to be any regular language and \(𝐿_1\), \(𝐿_2\) be any two context-free languages.
Which of the following is correct?
- A.
\(\overline{L_1}\)is context free - B.
\(\overline{(L_1 \cup L_2)} – R\)is context free - C.
\(L_1 \cap L_2\)is context free - D.
\(L_1 – R\)is context free
Attempted by 22 students.
Show answer & explanation
Correct answer: D
Correct statement: L1 - R is a context-free language.
Reasoning: L1 - R can be rewritten as L1 ∩ complement(R).
Regular languages are closed under complementation, so complement(R) is regular.
The intersection of a context-free language with a regular language is always context-free.
Therefore L1 ∩ complement(R) is context-free, so L1 - R is context-free.
Why the other statements fail (briefly):
The complement of a context-free language need not be context-free. Example: L1 = { a^n b^n | n ≥ 0 } is context-free, but its complement over {a,b}* is not context-free.
The intersection of two context-free languages need not be context-free. Example: L1 = { a^n b^n c^m | n,m ≥ 0 } and L2 = { a^m b^n c^n | m,n ≥ 0 } are context-free, but their intersection is { a^n b^n c^n | n ≥ 0 }, which is not context-free.
An expression like complement(L1 ∪ L2) - R need not be context-free. For instance, choose R = ∅ (which is regular); the expression reduces to complement(L1 ∪ L2), and complements of unions of CFLs can be non-context-free (use L1 = { a^n b^n } and L2 = ∅ ).
Conclusion: Only the statement that L1 - R is context-free is guaranteed by standard closure properties.
A video solution is available for this question — log in and enroll to watch it.