If L₁ is a context-free language and L₂ is a regular language, which of the…
1999
If L₁ is a context-free language and L₂ is a regular language, which of the following statements is/are false?
a. L₁ - L₂ is not context-free.
b. L₁ ∩ L₂ is context-free.
c. ~L₁ is context-free.
d. ~L₂ is regular.
- A.
Only b
- B.
Only c
- C.
Both a and c
- D.
Both b and c
Attempted by 7 students.
Show answer & explanation
Correct answer: C
Analyze each statement using closure properties. Since L₂ is regular, ~L₂ is also regular. Therefore, L₁ - L₂ = L₁ ∩ ~L₂ is context-free because CFLs are closed under intersection with regular languages. So statement a is false. Statement b is true for the same closure property. Statement c is false because CFLs are not closed under complement. Statement d is true because regular languages are closed under complement. Hence, the false statements are a and c.