Question

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 one of the following represents the language generated by the above grammar?
1. {(ab)ⁿ (cb)ⁿ | n ≥ 1}
2. {(ab)ⁿ cb^m1 cb^m2 … cb^mn |n, m₁, m₂ … , m_n ≥ 1}
3. {(ab)ⁿ (cb^m)ⁿ | m, n ≥ 1}
4. {(ab)ⁿ (cbⁿ)^m | m, n ≥ 1}

Answer 1

Correct Answer - Option 2 : {(ab)ⁿ cb^m1 cb^m2 … cb^mn |n, m₁, m₂ … , m_n ≥ 1}

String Derivation:

S → abScT

→ ababScTcT (∵ S → abScT)

→ abababcTcTcT (∵ S → abcT)

→ abababcbTcTcT (∵ T → bT)

→ abababcbbTcTcT (∵ T → bT)

→ abababcbbbTcTcT (∵ T → bT)

→ abababcbbbbcTcT (∵ T → b)

→ abababcbbbbcbcT (∵ T → b)

→ abababcbbbbcbcbT (∵ T → bT)

→ abababcbbbbcbcbb (∵ T → b)

abababcbbbbcbcbb = (ab)³cb⁴cbcb²

From this string, it is clear that all the option 1),3) and 4) are not generated by given grammar.

Only option 2 matches.