1
$\begingroup$

Giving the following Grammar:

S → ^ | SaSMSM |  SMSaSM | SMSMSa   
M → b | c


^ means eopsilon.

How can i check whether its ambgious or not? My intuition is that its not: every time you derive,the a is placed in different places between the M's.

Can you give me a clue to get a better prove? Or give an example for its ambiguity?

In other words,Can i have to different derevation trees for a same string in this grammar?
Thank you.

Improve this question
$\endgroup$
6
  • $\begingroup$ Have you seen this question? Have you tried the technique from the answer? $\endgroup$
    – Raphael
    Commented Apr 11, 2014 at 10:58
  • $\begingroup$ What is the definition of ambiguity? just apply it. Are there ... such that ... . If yes then ... If no then ... But remember that algorithms may have a hard time saying no, unless the problem is finite (which is not the case here). $\endgroup$
    – babou
    Commented Apr 11, 2014 at 10:58
  • $\begingroup$ I believe you can simplify that grammar. Look at the role of b and c. Do you need both ? can you simplify the rules? This actually requires proof, but the proof is not (yet?) needed if you see that as hints toward an answer. I do not know the asnswer off-hand, but I am guessing. $\endgroup$
    – babou
    Commented Apr 11, 2014 at 11:19
  • $\begingroup$ Well, the answer is given now ... but, still look at my suggestion. The answer is much easier to find when you simplify the grammar, if you can without impacting ambiguity. Note that the answer given does not use c. $\endgroup$
    – babou
    Commented Apr 11, 2014 at 11:31
  • $\begingroup$ @babou. In this grammar you can simply treat $M$ as a terminal symbol for ambiguity analysis. From the wording of the question I'd guess that Anton already noted this. $\endgroup$
    – FrankW
    Commented Apr 11, 2014 at 11:32

1 Answer 1

Reset to default
3
$\begingroup$

The grammar is ambiguous. The word $abbabb$ can be derived in at least 3 ways:

$$S \Rightarrow SaSMSM \Rightarrow^2 SaMM \Rightarrow SaSMSMaMM \Rightarrow^7 abbabb,$$ $$S \Rightarrow SaSMSM \Rightarrow^2 aSMM \Rightarrow aSMSMSaMM \Rightarrow^7 abbabb,$$ $$S \Rightarrow SaSMSM \Rightarrow^2 aMSM \Rightarrow aMSMSaSMM \Rightarrow^7 abbabb.$$

I found this by thinking about how words in the language might be parsed. My first observation was that if a word ends with $a$, the derivation must have started with the last rule for $S$. If it ends with $b$ or $c$ one of the other non-$\epsilon$-rules must have been used in the first step.

In order to distinguish these two rules, I looked at the preceding symbol, which is $S$ for both rules. The symbol before that differs again. So if we could uniquely identify the word resulting from the $S$ we could determine the initial rule unambiguously. If we furthermore could uniquely identify which subword results from which symbol of the rule in each case, we would get a procedure that yields a unique parse tree for each word, proving unambiguity.

Alas, I noted that it is not possible to uniquely determine the yield of the rightmost $S$. But now I had a better idea, how an ambiguous word should look like.

Improve this answer
$\endgroup$

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.