Gate CS-2017-1 Question Paper With Solutions

Q. 34 Consider the following context-free grammar over the alphabet ∑ = {a, b, c} with S as the start symbol:

S → abScT | abcT
T → bT | b

Which of the following represents the language generated by the above grammar?

(A) {(ab)ⁿ(cb)ⁿ | n >= 1 }

(B) {(abⁿcb^m₁cb^m₂…cb^m_n | n, m₁, m₂, ….., m_n >= 1 }

(C) {(ab)ⁿ(cb^m)ⁿ | n >= 1 }

(D) {(ab)ⁿ(cbⁿ)^m | m, n >= 1 }

Answer: (B)

Explanation: