I stumbled on this ambiguous grammar and I've been trying to make it unambiguous but it's still ambiguous.

Given the ambiguous CFG :
$S \to A\mid B$
$A \to aAb\mid ab$
$B \to abB\mid \epsilon$

My closet try was:

Given the ambiguous CFG :
$S \to A$
$A \to aAb\mid C$
$B \to b$
$C \to abC\mid\epsilon$

But the string "$ab$" is ambiguous

  • $\begingroup$ What have you tried? Where did you get stuck? Here is a good series of questions to get you started: cs.stackexchange.com/questions/tagged/… $\endgroup$ – dkaeae Jan 17 '19 at 12:53
  • $\begingroup$ In fact, the original CFG does not generate generate $aababb$, which is generated by your CFG as follows, $S\Rightarrow A\Rightarrow aAb\Rightarrow aCb\Rightarrow aabCb\Rightarrow aababCb\Rightarrow aababb$. $\endgroup$ – John L. Jan 17 '19 at 18:34
  • $\begingroup$ Oh true, those that mean there isn't a solution to this? $\endgroup$ – Owonubi Job Sunday Jan 17 '19 at 19:00

As you have observed, the only problem in the original CFG is that the string $ab$ can be generated by both $A$ and $B$.

Here is a hint. Instead of generating $ab, a^2b^2, a^3b^3,\cdots$, can you let $A$ generate $a^2b^2, a^3b^3,\cdots$ without generating $ab$?

| cite | improve this answer | |
  • $\begingroup$ Any idea on how to implement that? $\endgroup$ – Owonubi Job Sunday Jan 17 '19 at 15:54
  • $\begingroup$ How did you avoid an ambiguous parse of the empty string? $\endgroup$ – rici Jan 17 '19 at 16:37
  • $\begingroup$ @OwonubiJobSunday Instead of $A\to aAb\mid ab$, how about $A\to aAb\mid a^2b^2$? $\endgroup$ – John L. Jan 17 '19 at 16:41
  • $\begingroup$ @rici can the empty string be parsed in two ways in the original CFG? $\endgroup$ – John L. Jan 17 '19 at 16:43
  • $\begingroup$ @apass.jack. no, it can't. Why not? Because the base productions differ. $\endgroup$ – rici Jan 17 '19 at 16:47

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.