0
$\begingroup$

S->aAB

A->bBb

B->A|epsilon

It seems that the string abbbb can be derived by using more than one ways. After using the starting production and the production for A, we get: S=>abBbB.

From here, either of the B's can be replaced with epsilon and the other one replaced with bBb. So, there are two ways of deriving abbbb.

Isn't this ambiguous grammar?

It's a question from Formal Languages and Automata by Peter Linz (5th edition) Exercise 5.2.16

|cite|improve this question
$\endgroup$
  • $\begingroup$ What did you try? Where did you get stuck? We're happy to help you understand the concepts but just solving exercises for you is unlikely to achieve that. See also meta.cs.stackexchange.com/q/1284/755. Your first step is to look at the definition of "ambiguous grammar" and see how it applies here. Did you try that? What happened when you tried to follow that approach? $\endgroup$ – D.W.♦ Sep 15 '16 at 4:16
  • $\begingroup$ @D.W. I already mentioned what I tried. I tried to create two "different" ways of generating the string (which may be wrong hence, the confusion). $\endgroup$ – aste123 Sep 15 '16 at 5:52
2
$\begingroup$

You need to revisit the definition of ambiguity. The point is not whether multiple derivations exist; all non-linear grammars have many derivations per word. You have to check if there is only one left-derivation per word. Equivalently, you can check right-derivations or syntax trees.

If you think this grammar is ambiguous, prove it by giving two different syntax trees for some word.

If you think it is unambiguous, see here for how to prove that; it's often more tricky.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ As I mentioned in my question, we can reach at S=>abBbB. If I draw the parse tree, I get two trees but they seem synonymous to one another. Using that we can say it is unambiguous. But my confusion is that when the machine is parsing the string, how would it know which path to go? Doesn't this look like ambiguity even though the parse trees look synonymous? $\endgroup$ – aste123 Sep 14 '16 at 13:10
  • 1
    $\begingroup$ 1) What does "synonymous" mean for you? 2) No, you can not use that. You have to show that all words have only one parse tree each. 3) Non-determinism (which can't be implemented) or backtracking (which can be). 4) No, non-determinism and amiguity are not the same. $\endgroup$ – Raphael♦ Sep 14 '16 at 13:26
  • $\begingroup$ I meant isomorphic graphs and that it is unambiguous for string abbbb. I understand that it has to be shown for every word in case of unambiguous language. If I look at only left most derivation, then `S=>aAB=>abBbB. From left, we have seen only one b till now, would the parser take its next action based on the single b it has seen or would it have the knowledge of all the b's on the right side also? Since, there is a constant rule for the ambiguity, I guess, there has to be a constant rule for the parsing also. It seems confusing to me.. $\endgroup$ – aste123 Sep 15 '16 at 5:52
  • $\begingroup$ @aste123 Isomorphic is too weak. Parse trees are ordered trees; if you need to reorder children to match them, they are two distinct trees for the purpose of ambiguity. If that confuses you, use the definition with left-most derivations. $\endgroup$ – Raphael♦ Sep 15 '16 at 10:48
  • $\begingroup$ @aste123 As for parsers, that's a whole new bucket of theory I'm not sure you are ready for. Common deterministic linear-time parsing strategies do not cover all of DCFL even, let alone CFL. If you want to look into that, search for LL(k) and LR(k) parsing. (We also have lr-k and ll-k.) $\endgroup$ – Raphael♦ Sep 15 '16 at 10:50

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.