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 ?

  1. A.

    L1 ∩ L2 is context free

  2. B.

    L1 ∩ L2 is Regular

  3. C.

    L1 ∩ L2 is Recursively Enumerable and
    L1 ∩ L2 is Context Sensitive

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

Explore the full course: Mppsc Assistant Professor