Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Context-free grammar: derivations and ambiguity

  1. Jan 22, 2007 #1
    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?

  2. jcsd
  3. Jan 23, 2007 #2
    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.
  4. Jan 23, 2007 #3
    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?
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook