Gate CS-2010 Question Paper With Solutions

Q. 54 Consider the language

L1 = {0ⁱ1^j | i != j}.
L2 = {0ⁱ1^j | i = j}.
L3 = {0ⁱ1^j | i = 2j+1}.
L4 = {0ⁱ1^j | i != 2j}.

Which one of the following statements is true ?

(A) Only L2 is context free

(B) Only L2 and L3 are context free

(C) Only L1 and L2 are context free

(D) All are context free

Answer: (D)

Explanation: