My approach to a CFG

74 Views Asked by At

this site has been of great help, and I am certainly indebted to your assistance.

I was solving a question, $a^i b^j$ where $0\le i\le j\le 2\cdot i$

And here is my approach:

$S\to aSb \;|\; aSbb \;|\;e$

Did I solve the problem? What are usually common test cases to ensure it produces the proper grammar, I tried both low values for $i$, $j$, same values for $i$, $j$, and I received my expected output, but from my prior experience, receiving proper output does NOT imply I solved the question.

Thanks!

1

There are 1 best solutions below

4
On BEST ANSWER

It looks right. If I always choose the first option, then I have as many $a$ as $b$. If I always choose the second, then I have twice as many $b$ as $a$. Mixing them will clearly give me values within that range, which is all the question asks for. To construct a specific string $a^Ib^J$ with $I$ and $J$ specified, we need to pick $n$ of the first option and $m$ of the second such that:

$$n+m=I$$ $$n+2m=J$$

this gives $m=J-I, n=2I-J$. $n,m\geq 0$ implies that $I\leq J\leq 2I$, which is consistent with the boundaries in the question. So you can represent everything you were asked to (since we have an explicit procedure for doing so), and nothing you weren't (because of the upper bounds in the first paragraph), so it's solved.