Cheap and Secure Web Hosting Provider : See Now

# [Solved]: Is showing two different derivations enough to prove that a CFG is ambiguous?

, ,
Problem Detail:

I'm wondering, is showing two different ways to derive the same word enough proof to show that a context-free grammar is ambiguous?

For example:

O = start symbol
Non-terminal = {O}
Terminal = {r, s}
Productions =
O -> r
O -> Or
O -> sOO
O -> OOs
O -> OsO

There are two different derivations for the word rsrrs:

O -> OOs -> OsOOs -> rsOOs -> rsrOs -> rsrrs
O -> OsO -> rsO -> rsOOs -> rsrOs -> rsrrs

#### Answered By : jmite

As Rick says, this is very close. The key is to show that there are two different parse-trees for the same word in the grammar.

What you have is okay, but presenting it as a linear derivation isn't enough. For example, consider something similar to what you did, but slightly different:

$O \rightarrow OOs \rightarrow OsOOs \rightarrow rsOOs \rightarrow rsrOs \rightarrow rsrrs$

$O \rightarrow OOs \rightarrow rOs \rightarrow rsOOs \rightarrow rsrOs \rightarrow rsrrs$

At face value, these are two different derivations. However, if you look closely, you see that they only differ in the order that we expand the different terminals of the same intermediate word. So this is NOT a valid proof that the grammar is ambiguous.

However, if we look at your original example using parse-trees, we can see that it still holds:

O | O--O--s |  |   r  s--O--O       |  r       r

And the second tree:

O | O--s--O |     |   r     O--O--s       |  |       r  r

This shows that these are actually different parses: we use a different production from the initial $O$ symbol, so we know that they are different.

An equivalent way to do this is to use the linear derivations like you do, but always put them in "left-derivative" form, where you only ever expand the left-most non-terminal. So your derivations would become:

$O \rightarrow OOs \rightarrow rOs \rightarrow rsOOs \rightarrow rsrOs \rightarrow rsrrs$

$O \rightarrow OsO \rightarrow rsO \rightarrow rsOOs \rightarrow rsrOs \rightarrow rsrrs$

In this case, there's a 1:1 correspondence between left-derivatives and parse trees, so if there are two distinct ones, you know the grammar is ambiguous.

For the "bad" example I gave, both derivations give the first parse tree, so it's not a valid proof that the grammar is ambiguous.

###### Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/48821

3.2K people like this