0
$\begingroup$

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.

Improve this question
$\endgroup$
6
  • $\begingroup$ See answer here: stackoverflow.com/questions/15559324/… $\endgroup$
    – Ran G.
    Commented Apr 6, 2013 at 18:21
  • 2
    $\begingroup$ and here: cs.stackexchange.com/questions/9804/… $\endgroup$
    – Ran G.
    Commented Apr 6, 2013 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.
    Commented Apr 6, 2013 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.
    Commented Apr 6, 2013 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
    Commented Apr 6, 2013 at 19:28

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$

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