If L1 and L2 are context free languages, which of the following is True about…
2024
If L1 and L2 are context free languages, which of the following is True about L1 ∩ L2 ?
- A.
L1 ∩ L2 is context free
- B.
L1 ∩ L2 is Regular
- C.
L1 ∩ L2 is Recursively Enumerable and
L1 ∩ L2 is Context Sensitive - D.
None
Attempted by 29 students.
Show answer & explanation
Correct answer: C
Let L1L_1L1 and L2L_2L2 be context-free languages (CFLs).
1️⃣ Is the intersection of two CFLs context-free?
No.
Context-free languages are not closed under intersection.
Example:
L1={aibicj∣i,j≥0}L_1 = \{ a^i b^i c^j \mid i,j \ge 0 \}L1={aibicj∣i,j≥0}
L2={aibjcj∣i,j≥0}L_2 = \{ a^i b^j c^j \mid i,j \ge 0 \}L2={aibjcj∣i,j≥0}
L1∩L2={anbncn∣n≥0}L_1 \cap L_2 = \{ a^n b^n c^n \mid n \ge 0 \}L1∩L2={anbncn∣n≥0},
which is not context-free.
A video solution is available for this question — log in and enroll to watch it.