Consider a CFG with the following productions. S → AA | B A → 0A | A0 | 1 B →…

GATE · 2008 · IT· Modified — slightly modified from the official paper; see the solution

1. A.

   {0n 102n | n ≥ 1}

2. B.

   {0^i 1 0^j 1 0^k | i,j,k ≥ 0} ∪ {0^n 1 0^(2n) | n ≥ 0}

3. C.

   {0i 10j | i, j ≥ 0} ∪ {0n 102n | n ≥ l}

4. D.

   The set of all strings over {0, 1} containing at least two 0\'s

Attempted by 32 students.

The worked solution is available to enrolled students.

Video solution available to enrolled students.