Which is correct ?

2006

GATECS2006Q18

Which is correct ?

  1. A.

    L1 only

  2. B.

    L3 Only

  3. C.

    L1 and L2

  4. D.

    L2 and L3

Attempted by 21 students.

Show answer & explanation

Correct answer: D

L₁ is context-free because it can be generated by a CFG with rules like S → 0S1 | ε, producing strings of the form 0ⁿ1ᵐ. L₂ is not context-free because it requires matching three variables (n, m, n+m) which cannot be handled by a single stack. L₃ is also not context-free as it requires counting 0s, then 1s, and then matching the total count of 0s with a later block of 0s, which exceeds the capability of a PDA. Therefore, L₂ and L₃ are not context-free.

A video solution is available for this question — log in and enroll to watch it.

Explore the full course: Gate Guidance By Sanchit Sir

Loading lesson…