- #1
KataKoniK
- 1,347
- 0
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.
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.