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

Problem Detail: 

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.

Asked By : Gaak

Answered By : Raphael

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/11076