Describe the language generated by this context-free grammar

Question

I have the following grammar,

1. S -> Sb
2. S -> aaSb
3. S -> b

The typical derivations in this grammar are
S => Sb => [aaSb]b => [aa[b]b]b => aabbb for n = 1
S => Sb => [aaSb]b => [aa[aaSb]b]b => [aa[aabb]b]b => aaaabbbb for n = 2

Edit: So I claimed that this grammar generates the language
L = {a^(2n)b^(n+2) : n >= 1}

I am pretty sure that my a goes a^(2n) since there's two a before S, but what about b. There is no lambda here so my n goes from n >= 1?.

Edit:
b^(n+1) and b^(2n+1) are both wrong assumptions because the grammar can derive a string aaaaaabbbbb if n = 3.
I modified my b to be b^(n+2). so that L becomes L = {a^(2n)b^(n+2) : n >= 1}

Answer 1

The language generated by this grammar is a^(2n) b^(n+m+1) where n and m are natural numbers. To show this, (a) we see that any string derived using the grammar's productions matches the above and (b) any string matching the above can be derived using the grammar's productions.

(a) The grammar can and must use rule (3) exactly once. This gives the +1 in the number of bs. Execution of rule (2) can happen some number of times n, putting 2n as on the front and n bs on the back, hence the 2n and n terms. Rule (1) can be executed any number of times m, hence the term.

(b) Given a string a^(2n) b^(n+m+1) for natural numbers n and m: use rule (1) a number of times equal to m; then, use rule (2) a number of times equal to n; then, user rule (3) once. Thus, the grammar generates the string.

Another way to write the same answer is a^2n b^m with m > n.

Answer 2

One way to tackle this is to rewrite the grammar. Note that productions 1 and 2 both end in Sb, so we can left-factor them:

S -> ASb
S -> b
A -> 
A -> aa

From the first two productions, it's fairly easy to see that S generates A^n b^{n+1} for n >= 0.

From the last two productions, A^n generates a^{2k} for 0 <= k <= n.

So the language is a^{2k} b^{n+1} for n >= 0, 0 <= k <= n.

Or equivalently, let m = n - k to obtain a^{2k} b^{k+m+1} for k,m >= 0.