could you please help me for finding an unambiguous CFG for the following expression: $a^ib^j$ where $i \le j \le 2i$
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$– FrankWCommented 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$– babouCommented Sep 5, 2014 at 20:57
-
$\begingroup$ Already came up with some ideas none of them is unambiguous... $\endgroup$– suatCommented 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$– Hendrik JanCommented 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$– babouCommented Sep 6, 2014 at 7:20
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
5
$S \rightarrow$ $aSb$ | $J$
$J \rightarrow aJbb$ | $ε$
This has only one derivation tree for a word in that language.
-
$\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$– suatCommented 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$– suatCommented Sep 6, 2014 at 7:11
-
$\begingroup$ You were right before. See edit $\endgroup$ Commented 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$– suatCommented 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$ Commented Sep 7, 2014 at 4:21