Context Free Grammar Design

Question

I'm learning about Context Free Grammars, and I've been understanding them so far, but this problem is kind of making my head spin.

I have the following rules:

S --> aSb | bB | epsilon
B --> bbB | bB | epsilon

And I'm almost certain that they are incorrect. I understand how I would do just i <= j instead of the actual language, but the idea of doing j <= 3i is really hard to grasp for me and I don't really understand how I should represent that in a CFG.

I've read some questions and threads on here about designing CFG, but they didn't really help me with a strategy to determine the answer.

Thanks in advance for your help!

Answer 1

For any a in a string you have to have 1, 2, or 3 bs in the string.

The bs have to follow the as.

You can have zero as.

S = A S B | e
A = a
B = b | bb | bbb

Zero as implies no bs.

One a allows for 1, 2, or 3 bs.

Through recursion through S you can have any number of as.

Answer 2

Your solution is indeed incorrect, because the condition j <= 3i is not obeyed.

A solution that is closer to your intent than the one from Björn, and that uses less non-terminals:

S -> aSb | aSbb | aSbbb | epsilon