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!

  • $\begingroup$ Welcome to COMPUTERSCIENCE @SE. What exactly make you think this is not even close? Is $b$ in the language of the grammar above? $\endgroup$
    – greybeard
    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 \;\}$


I'll explain my thought process behind thinking about this problem here:

-> 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.


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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.