Context free grammar over { a^n * b^(n+3) | n >= 0 }

Question

Context free grammar over { a^n * b^(n+3) | n >= 0 }

So far I have this, but I don't think it's entirely correct

S --> aSbS | TbTbTb

T --> aTbT | lambda

Is the aSbS even necessary?

SOLUTION

S --> aSb | Tbbb

T --> aTb | lambda

Answer 1

What you have isn’t close, I’m afraid. You need to make sure that each time the grammar generates an $a$ on the left, it also generates a $b$ on the right. If the language were $\{a^nb^n:n\ge 0\}$, we could do it with $S\to aSb\mid\lambda$: applying the first production $n$ times for $n\ge 0$ would produce $a^nSb^n$, and then applying the second would produce $a^nb^n$. Can you see how to make just a small modification to this grammar to make it generate your language instead?