# CFG for $\{a^i b^j : 2 i<j\}$ [duplicate]

So I have a question:

Give a CFG for $\{a^i b^j : 2 i<j\}$

And this is my approach:

$S\to AB$

$A\to aAb\mid \varepsilon$

$B\to b \mid bB$

A confirmation, or correction, along with how you tested(and tips for testing future of my problems) will be greatly appreciated thanks.

• See answer here: stackoverflow.com/questions/15559324/… – Ran G. Apr 6 '13 at 18:21
• – Ran G. Apr 6 '13 at 18:24
• and a bit more sophisticated variant here: cs.stackexchange.com/questions/9831/… so I recommend to close this question since it is essentially a duplicate. – Ran G. Apr 6 '13 at 18:27
• Gaak, your approach doesn't work. To understand how the correct grammar works, please see the links. Do compare your approach to the grammars given there - this will surely give you insights regarding what is wrong with your answer and how to amend it. Use the search feature to find other examples (since many users asked this very similar question before you - a lot of information already exists on this site, and it is redundant to re-iterate it from scratch.) – Ran G. Apr 6 '13 at 18:43
• The question metioned by @RanG. isn't an exact match, but your problem is solved by one part of the solution. – vonbrand Apr 6 '13 at 19:28

You can derive $aabbb$ which is not in the language, so your grammar is wrong.

How did I find this? I observed that $A \Rightarrow^* a^ib^i$ and $B \Rightarrow^* b^j$ for all $i \geq 0$, $j > 0$. It's clear that this is wrong, and I looked for the smallest counter-example.

You need to ensure that more than double as many $b$'s as $a$'s are generated.