Search code examples
context-free-grammarcontext-free-languageautomata-theory

Context Free Grammar Design

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.

Description of language

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!

Solution

  • 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.