# Context-free grammar for $L=\{ a^nb^m | n \le m+3 \}$

I'm having problems determining the productions for a CFG describing the language $$L=\{ a^nb^m | n \le m+3 \}$$

where $$n,m \ge 0$$

I'm very new to this so this example might be a little harder, but everything I try I end up not finding the correct solutions. Some example strings are $$\epsilon$$, $$a$$, $$aa$$, $$aaa$$, $$b$$, $$ab$$, $$aab$$, $$aaab$$, $$aaaab$$, $$bb$$, $$abb$$, $$aabb$$, $$aaabb$$, $$aaaabb$$, $$aaaaabb$$ etc.

This is how I tried reasoning:

since there can be a loop of $$a$$ in the beginning, I thought that one production could be

$$A \rightarrow aAb | \epsilon$$

But this is as far as my reasoning goes. What's confusing is that for each value of $$m$$, I have increasing $$n$$.

Can anyone give a hint, or give general hints how to construct CFG from languages?

Thanks!

• Hint: $L = a^n b^n\,bbb\,b^*$ May 29 at 10:51
• @Pseudonym This gives $m \ge n+3$. May 29 at 12:26
• @YuvalFilmus Is that supposed to be a regular expression? Since we have $a^nb^n$ and $b*$ combined what is the difference between, say, $b^n$ and $b*$ in this regexp? May 29 at 12:36
• The intended interpretation is $\bigcup_n a^nb^nbbbb^*$ May 29 at 12:36
• @YuvalFilmus Ah, yes, sorry. Even though I got it the wrong way around, the hint stands as a hint. May 29 at 23:44 $$S \rightarrow aSb/A$$
$$A \rightarrow \epsilon/a/aa/aaa/B$$
$$B \rightarrow bB/\epsilon$$