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$
  • $\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 '14 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 '14 at 20:57
  • $\begingroup$ Already came up with some ideas none of them is unambiguous... $\endgroup$ – suat Sep 5 '14 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$ – Hendrik Jan Sep 5 '14 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 '14 at 7:20
3
$\begingroup$

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

$J \rightarrow aJbb$ | $ε$

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

$\endgroup$
  • $\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 '14 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 '14 at 7:11
  • $\begingroup$ You were right before. See edit $\endgroup$ – d'alar'cop Sep 6 '14 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 '14 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 '14 at 4:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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