# Context free grammar for $L=\{a^nb^m : 2m<n<4m\}$

The thing that confuses me here is that i've seen a similar example where $$L=\{a^nb^m : 2m\leq n\leq 4m\}$$ where the CFG was straight forward: $$S\rightarrow aSbb\\ S\rightarrow aSbbb\\S\rightarrow aSbbbb\\S\rightarrow \epsilon$$ however, in this example I cant get my mind out of the "just go for the simple approach" which is $$S\rightarrow aSbbb\\S\rightarrow\epsilon$$ however this feels somewhat incomplete to me.

EDIT: I see my errors, i propose this solution: $$S\rightarrow aaaAb\\A\rightarrow aaaAb\\A\rightarrow \epsilon$$ this seems more correct due to the fact that now I am 'forcing' 3 $$a$$'s each time a $$b$$ shows up, also $$\epsilon$$ is no longer included.

• I think you swaped the roles of $n$ and $m$ in the condition of the language. Feb 20 at 17:33
• @Nathaniel Indeed, It seems that I've misread the language definition, I have fixed my solution. Feb 20 at 17:44
• Please include the question in the body of your question. The title should help people find this page via search, but is not a replacement for stating the question in the body of the post.
– D.W.
Feb 20 at 17:51
• Please don't use "EDIT:". Please revise your question so it reads well for someone who encounters it for the first time, then flag comments as 'no longer needed'. See cs.meta.stackexchange.com/q/657/755. I encourage you to revise your question accordingly. I have given you similar feedback before: cs.stackexchange.com/questions/160059/#comment334941_160059
– D.W.
Feb 20 at 17:54
• Please don't edit your question in a way that invalidates existing answers. If you discover that you asked the wrong question, then please take that as a lesson to exercise more care in the construction of your questions in the future, to proof-read them to make sure you are asking what you want to ask, and ask a new question.
– D.W.
Feb 20 at 17:55

The problem with your (new) solution is that you force $$n$$ to be equal to $$3m$$. That means that your grammar generates words that are in $$L = \{a^nb^m\mid 2m < n < 4m\}$$, but words in $$L$$ like $$aaaaabb$$ cannot be generated by your grammar.
• for each $$b$$, one must add $$2$$, $$3$$ or $$4$$ $$a$$'s;
• one must neither always add $$2$$ $$a$$'s, nor always add $$4$$ $$a$$'s.
• So a first rule $S\rightarrow aaaAb$ followed by the second rule $A\rightarrow aaAb | aaaAb | aaaaAb | \epsilon$ should be the right approach? Feb 21 at 14:32
No. The grammar you propose is not correct. For example it generates $$\varepsilon$$, which is not in the language. In fact, no word generated by your grammar is in the language. To see this notice that the generated words have at least as many $$b$$s than $$a$$s, yet all words in the language have more $$a$$s than $$b$$s.