2

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!

apnorton
  • 17,706
Gaak
  • 221
  • I've edited your question to use $\LaTeX$. Please make sure it still represents your original intent.... :) – apnorton Apr 06 '13 at 17:54

1 Answers1

1

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.

Robert Mastragostino
  • 15,727
  • I appreciate your time for analyzing my question. It wouldve bothered me to not know if I solved it right or wrong :) – Gaak Apr 06 '13 at 18:00
  • Thanks! I'd wait a bit before you accept the answer though; you might get some more comments from people who know the area far better than me if you leave it open for a while. – Robert Mastragostino Apr 06 '13 at 18:01
  • Ok sir, wil do. – Gaak Apr 06 '13 at 18:03
  • @Gaak, you can, and perhaps should, upvote this questions (up-arrow), even if you decide to wait a little to accept it. ] – DonAntonio Apr 06 '13 at 19:40