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

4.3k Views Asked by At

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.

1

There are 1 best solutions below

0
On

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$$