1
$\begingroup$

could you please help me for finding an unambiguous CFG for the following expression: $a^ib^j$ where $i \le j \le 2i$

$\endgroup$
5
  • $\begingroup$ Welcome to Computer Science! Note that you can use LaTeX here to typeset mathematics in a more readable way. See here for a short introduction. (I have edited your post accordingly.) $\endgroup$
    – FrankW
    Sep 5, 2014 at 20:22
  • 1
    $\begingroup$ Hint. Try to do it for j=i, Then try to do it for j=2i. That should give you a feel for the problem. $\endgroup$
    – babou
    Sep 5, 2014 at 20:57
  • $\begingroup$ Already came up with some ideas none of them is unambiguous... $\endgroup$
    – suat
    Sep 5, 2014 at 23:24
  • $\begingroup$ Nice question. The ambiguous solution is given elsewhere on this site. Now get some order on the two "competing" productions. Like the question, sonce the language is an example that cannot be accepted by a deterministic PDA. $\endgroup$ Sep 5, 2014 at 23:59
  • 1
    $\begingroup$ If you told us what you tried, we might better understand how to help you. Just giving you the answer would not teach you anything. Did uou try my suggestions, or the suggestion of Jan Hendrik? $\endgroup$
    – babou
    Sep 6, 2014 at 7:20

1 Answer 1

3
$\begingroup$

$S \rightarrow$ $aSb$ | $J$

$J \rightarrow aJbb$ | $ε$

This has only one derivation tree for a word in that language.

$\endgroup$
5
  • $\begingroup$ What about such a case: S => iSjJ => iiSjJjJ => iijJjJ => iijjjJ => iijjj and S => iSjJ => iiSjJjJ => iijJjJ => iijjJ => iijjj . Those two different derivations produce the same string $\endgroup$
    – suat
    Sep 6, 2014 at 5:08
  • $\begingroup$ Do you mean that it does not matter which J to be expanded to non-terminal or $ considering the ambiguity as long as the remaining part of the trees are the same? $\endgroup$
    – suat
    Sep 6, 2014 at 7:11
  • $\begingroup$ You were right before. See edit $\endgroup$
    – d'alar'cop
    Sep 6, 2014 at 13:12
  • $\begingroup$ Thanks for the answer. It seems OK now.. It seems simple but it would be hard to think about from scratch :) $\endgroup$
    – suat
    Sep 6, 2014 at 20:38
  • $\begingroup$ @suat Yes, I'm not sure about a generating algorithm. I can give you a tip though: Having only one non-terminal in the derivation at any time helps. Make it so that you can't "go back" to other non-terminal (notice in this example, that once you J you can't use S anymore). Finally, notice how S handles the balanced part of the word (and they would all have a part which is balanced), then J handles the unbalanced part (restricting the unbalance to 1:2). $\endgroup$
    – d'alar'cop
    Sep 7, 2014 at 4:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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