2
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • $\begingroup$ It seems this grammar is unambiguous after all. $\endgroup$
    – Yuval Filmus
    Commented Jun 18, 2017 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
    Commented Jun 18, 2017 at 14:36

1 Answer 1

Reset to default
-1
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ But why is that true? You have to explain. $\endgroup$
    – Yuval Filmus
    Commented Jun 18, 2017 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'
    Commented Aug 18, 2017 at 8:58

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.