# How can I efficiently construct a CFG from a language

I am new to CFG's and automata in general and I came across an exercise where I needed to construct a CFG for the language {a^m b^n | n <= m + 3}.

So m can be infinitely bigger than n but n can only be up to 3 more bigger than m and they can be the same. I have no idea how to make a CFG for this.

What I came up with was:

S -> AB | _
A -> a | aa | aaa | C | _
C -> aC | a | _
B -> bB | b | _


But I think this is not even close...

Any help/tips/advice would be much appreciated!

• Welcome to COMPUTERSCIENCE @SE. What exactly make you think this is not even close? Is $b$ in the language of the grammar above? Sep 11 '20 at 7:00

The best way is to learn is to look at examples, and see how they work.

One of the simplest "real" context-free languages is $$\{\; a^mb^n \mid n = m \;\}$$

Its grammar is $$S\to aSb\mid \varepsilon$$.

Now add in steps, the extra 3, and the more than ...

$$\{\; a^mb^n \mid n = m+3 \;\}$$

$$\{\; a^mb^n \mid n \le m+3 \;\}$$

-> With inequalities, I first think at the equality constraint. So I assume n = m+3

-> Now, n is always 3 more than m.

-> I split the problem further. I think to myself okay, let's have one production handle equal production of a and b.

-> How many more b's do we need after this? ( 3! )

-> I include that in the start symbol.

-> To end it, I know, n = m+3 is not a hard rule. It is <= . So, I make another production that produces infinite number of B's.

Grammar:

S -> Abbb
A -> aAb | B
B -> bB | e   ( e is lambda or epsilon )