Consider the grammar G: S → AbB, A → aAb | λ, B → bB | λ. Which language does G generate?

1. A{aⁿbᵐ : n ≥ 0, m > n}
2. B{aⁿbᵐ : n ≥ 0, m ≥ 0}
3. C{aⁿbᵐ : n ≥ m}
4. D{aⁿbᵐ : n ≥ m, m > 0}

Pick an option to check yourself, or open the answer below.

Show answer & explanation

Correct answer: A. {aⁿbᵐ : n ≥ 0, m > n}

Explanation

A gives aⁿbⁿ, then a mandatory b, then B gives any number of b's: aⁿ b^(n+1+k). So m > n, n ≥ 0.