PDA

View Full Version : context-free grammar: derivations and ambiguity


KataKoniK
Jan22-07, 11:13 AM
I have a question regarding about CFGs, derivations, and ambiguity.

Say you are given some CFG that produces A, B, or C

You are able to come up with two different derivations for A

To say the CFG that produces A, B, or C is ambiguous, you must find two different parse trees for some string that is generated by that CFG. Wouldn't it be good enough to just draw the parse tress of the two derivations of A to say that the CFG is ambiguous? However, I was told that even if you find two different derivations of a string, it doesn't always follow that the CFG is ambiguous. Why is that the case? And how can you fully determine that a CFG is truly ambiguous regardless if you find two different derivations or not?

Thanks.

Jheriko
Jan23-07, 07:25 AM
Some parse trees are trivial modifications of others and result in the same effect, i could imagine that in order to show that it is ambiguous you need to show two parse trees from the same source which result in different effects.

KataKoniK
Jan23-07, 09:59 AM
Can I just draw the two parse trees of the two different derivations of the same string and come to the conclusion that the language is ambigious?