Gate CS-2018 Question Paper With Solutions

Q. 46 Consider the following languages:

I. {a^mbⁿc^pd^q ∣ m + p = n + q, where m, n, p, q ≥ 0}
II. {a^mbⁿc^pd^q ∣ m = n and p = q, where m, n, p, q ≥ 0}
III. {a^mbⁿc^pd^q ∣ m = n = p and p ≠ q, where m, n, p, q ≥ 0}
IV. {a^mbⁿc^pd^q ∣ mn = p + q, where m, n, p, q ≥ 0}

Which of the above languages are context-free?

(A) I and IV only

(B) I and II only

(C) II and III only

(D) II and IV only

Answer: (B)

Explanation: