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?

  1. A.

    \(\overline{L_1}\) is context free

  2. B.

    \(\overline{(L_1 \cup L_2)} – R\) is context free

  3. C.

    \(L_1 \cap L_2\) is context free

  4. 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.

Explore the full course: Mppsc Assistant Professor