I was given the following CFG :

$S \rightarrow A\ |\ B$

$A\rightarrow aAa\ |\ abAb\ |\ bAc\ |\ aca\ |\ abcb\ |\ bcc$

$B \rightarrow bBa\ |\ aBb\ |\ babBc\ |\ bca\ |\ acb\ |\ babcc$

And I have to show if it is ambiguous by giving two leftmost derivations for the same word.

I am pretty sure that there are two leftmost derivations but I can not find them.

I do not need the solution, just a tip where to start with would be enough.

  • $\begingroup$ It seems this grammar is unambiguous after all. $\endgroup$ – Yuval Filmus Jun 18 '17 at 13:37
  • $\begingroup$ I figured that out as well. I think I should start with A → abAb and end with bcc and start B → with aBb and end with babcc $\endgroup$ – Mattjo Jun 18 '17 at 14:36

Is unambiguous because there is no string of rule A which is a string or substring of B. And viceversa.

  • 1
    $\begingroup$ But why is that true? You have to explain. $\endgroup$ – Yuval Filmus Jun 18 '17 at 22:43
  • $\begingroup$ This is not enough to justify that the grammar is unambiguous. There could be more than one way to build an A using only A rules. $\endgroup$ – Gilles 'SO- stop being evil' Aug 18 '17 at 8:58

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.