Context-free grammar: derivations and ambiguity

  • Thread starter KataKoniK
  • Start date
  • #1
168
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.
 

Answers and Replies

  • #2
158
1
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.
 
  • #3
168
0
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?
 

Related Threads on Context-free grammar: derivations and ambiguity

Replies
2
Views
3K
  • Last Post
Replies
2
Views
3K
  • Last Post
Replies
5
Views
6K
Replies
0
Views
1K
  • Last Post
Replies
1
Views
5K
  • Last Post
Replies
7
Views
3K
  • Last Post
Replies
1
Views
2K
  • Last Post
2
Replies
27
Views
29K
  • Last Post
Replies
8
Views
855
Top