Showing a grammar to be ambiguous

351 Views Asked by At

I'm learning about grammar ambiguity and trying to show the following grammar is ambiguous:

$S \rightarrow ScS | SdS | A$

$A \rightarrow a | b$

I used 2 different left-derivations to get the same string $w=acb$, but I'm not sure I'm using the left-derivations properly:

a) $S \rightarrow ScS \rightarrow acS \rightarrow acA \rightarrow acb$

b) $S \rightarrow ScS \rightarrow AcS \rightarrow AcS \rightarrow acA \rightarrow acb$

Maybe someone can show me where I'm going wrong.

EDIT:

Based on the great answer below this seems more on track:

a) $S \rightarrow ScS \rightarrow AcS \rightarrow acS \rightarrow acSdS \rightarrow acAdS \rightarrow acbdA \rightarrow acbda$

b) $S \rightarrow SdS \rightarrow ScSdS \rightarrow AcSdS \rightarrow acSdS \rightarrow acAdS \rightarrow acbdS \rightarrow acbdA \rightarrow acbda$

1

There are 1 best solutions below

1
On BEST ANSWER

Your first derivation is missing a step ($ScS \rightarrow AcS$) and your second has an unnecessary step ($AcS \rightarrow AcS$). If you fix that the two derivations give the same parse tree and don't show the ambiguity. In fact as they don't use they second alternative in the production for $S$, they are in a sublanguage that is unambiguous.

To see that the grammar actually is ambigous, look at an example like $acbda$. This has two different parse trees (one that uses the rule $S \rightarrow ScS$ above the rule $S \rightarrow SdS$ and one that uses those rules the other way round).