# CFG for L {a^nb^m | n <= m+3}

I need a Context Free Grammar for this language. I could come up with this solution:

S -> AB
A -> aA | ε
B -> bbbB | ε


But, this grammar is clearly wrong, since the number of a's can still exceed the number of b's. How do I draw a link between the two variables A and B such that $$n\leq m+3$$?

P.S. It is a humble request to anyone who downvotes this question to please specify the reason in the comments below

• Create up to 3 a’s. Then repeatedly either create ab or b. Apr 28, 2019 at 15:14
• @gnasher729 sorry I couldn't get it, could you write an answer please? Apr 28, 2019 at 15:30

Based on gnasher729's comment, I came up with the following CFG that I believe meet the requirements:

$$S \to AAAB \\ A \to a \;|\; \varepsilon\\ B \to aBb \;|\; Bb \;|\; \varepsilon$$

• looks fine to me too Apr 28, 2019 at 16:42

It is hard to come up with a CFG directly. A better approach can be, making a PDA and converting the PDA to CFG. Refer to this answer.

• Huh? Took me 10 seconds to write down how to do it, and Acid probably not more than a minute to do it (and most of that time figuring out how to type an epsilon). Apr 28, 2019 at 23:18
• @gnasher729 maybe because you are more proficient at it? Apr 29, 2019 at 3:33
• @gnasher729 in case anyone of you has downvoted this question, please read the post again and do the needful Apr 29, 2019 at 3:37
• @gnasher729 I just pointed out a procedure to go about it. I personally had a hard time coming up with the grammars directly in the past. Apr 29, 2019 at 4:26
• @Infinity Yes, I am a cs undergrad at IITB. Apr 29, 2019 at 10:12

S-> aSb | bbb A grammar G=(V,T,S,P) is defined as V=s T=a,b S=s P=aSb|bbb