Which grammar generates L = {aⁿbⁿ⁻³ | n > 2} over Σ = {a, b}?

1. AS → aA|a, A → aAb|b
2. BS → aaA|λ, A → aAb|λ
3. CS → aaaA|a, A → aAb|λ
4. DS → aaaA, A → aAb ∣ λ

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

Show answer & explanation

Correct answer: D. S → aaaA, A → aAb ∣ λ

Explanation

aⁿbⁿ⁻³ = aaa · aᵏbᵏ with k = n − 3 ≥ 0. S → aaaA, A → aAb | λ produces exactly that.