# 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. – gnasher729 Apr 28 at 15:14
• @gnasher729 sorry I couldn't get it, could you write an answer please? – Infinity Apr 28 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 – Infinity Apr 28 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). – gnasher729 Apr 28 at 23:18
• @gnasher729 maybe because you are more proficient at it? – Infinity Apr 29 at 3:33
• @gnasher729 in case anyone of you has downvoted this question, please read the post again and do the needful – Infinity Apr 29 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. – SiluPanda Apr 29 at 4:26
• @SiluPanda hello sir! you are from iit b? – Infinity Apr 29 at 8:04