Finding a context-free grammar for $a^i b^j : 2i < j$

Question

So I have a question:

Give a CFG for $a^i b^j : 2i < j$.

And this is my approach:

$$S \to AB$$ $$A \to aAb | e$$ $$B \to b | bB$$

Thanks, a confirmation, or correction, along with how you tested (and tips for testing future problems of mine) will be greatly appreciated. Thanks.

@copper.hat I had less than 2*i < j but some how it didnt appear in the actual post — Gaak, Apr 06 '13 at 18:16
Guys, there is no need to downgrade the post, when it is not my fault that when I typed <j it somehow didn't show up(yet it was in the body of the text when I pressed edit. — Gaak, Apr 06 '13 at 18:17
CFG = College Football Gals ? Why to use such short writings that not everybody understands? — DonAntonio, Apr 06 '13 at 18:37

score 1 · Answer 1 · answered Apr 06 '13 at 19:29

The grammar above accepts $abb$ which doesn't satisfy the requirements.

If you work through a few examples, the pattern will become clear. The above accepts the language $a^i b^j$ where $i < j$. This might give a hint for an easy repair to the above grammar.

If not:

$$A \to aAbb | \epsilon$$

Finding a context-free grammar for $a^i b^j : 2i < j$

1 Answers1