0
$\begingroup$

This question already has an answer here:

So I have a question:

Give a CFG for $\{a^i b^j : 2 i<j\}$

And this is my approach:

$S\to AB$

$A\to aAb\mid \varepsilon$

$B\to b \mid bB$

A confirmation, or correction, along with how you tested(and tips for testing future of my problems) will be greatly appreciated thanks.

$\endgroup$

marked as duplicate by Ran G., vonbrand, frafl, Gilles 'SO- stop being evil' Apr 6 '13 at 20:35

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ See answer here: stackoverflow.com/questions/15559324/… $\endgroup$ – Ran G. Apr 6 '13 at 18:21
  • 2
    $\begingroup$ and here: cs.stackexchange.com/questions/9804/… $\endgroup$ – Ran G. Apr 6 '13 at 18:24
  • 1
    $\begingroup$ and a bit more sophisticated variant here: cs.stackexchange.com/questions/9831/… so I recommend to close this question since it is essentially a duplicate. $\endgroup$ – Ran G. Apr 6 '13 at 18:27
  • 1
    $\begingroup$ Gaak, your approach doesn't work. To understand how the correct grammar works, please see the links. Do compare your approach to the grammars given there - this will surely give you insights regarding what is wrong with your answer and how to amend it. Use the search feature to find other examples (since many users asked this very similar question before you - a lot of information already exists on this site, and it is redundant to re-iterate it from scratch.) $\endgroup$ – Ran G. Apr 6 '13 at 18:43
  • 1
    $\begingroup$ The question metioned by @RanG. isn't an exact match, but your problem is solved by one part of the solution. $\endgroup$ – vonbrand Apr 6 '13 at 19:28
0
$\begingroup$

You can derive $aabbb$ which is not in the language, so your grammar is wrong.

How did I find this? I observed that $A \Rightarrow^* a^ib^i$ and $B \Rightarrow^* b^j$ for all $i \geq 0$, $j > 0$. It's clear that this is wrong, and I looked for the smallest counter-example.

You need to ensure that more than double as many $b$'s as $a$'s are generated.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.