Context-free grammar: derivations and ambiguity

  • Thread starter KataKoniK
  • Start date
  • Tags
    Derivations
In summary, the conversation discusses the concept of CFGs, derivations, and ambiguity. It is mentioned that to determine if a CFG is ambiguous, two different parse trees must be found for a string generated by the CFG. However, it is also noted that finding two different derivations for a string does not always mean that the CFG is ambiguous. The conversation ends with a question about whether drawing two different parse trees for the same string is enough to conclude that the language is ambiguous.
  • #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.
 
Technology news on Phys.org
  • #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.
 
  • #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?
 

1. What is a context-free grammar?

A context-free grammar is a formal system used to describe the syntax or structure of a language. It consists of a set of production rules that define how symbols can be combined to form valid sentences in the language.

2. What is a derivation in context-free grammar?

A derivation is a sequence of steps that shows how a sentence in a language can be generated using the production rules of a context-free grammar. Each step involves replacing a non-terminal symbol with a sequence of symbols until only terminal symbols remain.

3. What is the difference between a leftmost and rightmost derivation?

In a leftmost derivation, the leftmost non-terminal symbol is always replaced in each step, while in a rightmost derivation, the rightmost non-terminal symbol is replaced. This results in different parse trees and can affect the meaning or structure of the sentence.

4. What is ambiguity in context-free grammar?

Ambiguity occurs when a sentence in a language can be derived in more than one way using the production rules of a context-free grammar. This can lead to multiple possible interpretations or meanings of the sentence.

5. How can ambiguity be resolved in context-free grammar?

Ambiguity can be resolved by either defining more specific production rules or by using a parsing algorithm, such as the CYK algorithm, to determine the most likely interpretation of the sentence. Another approach is to use semantic analysis to determine the intended meaning of the sentence.

Similar threads

MHB Grammars and regular expressions.
    • Programming and Computer Science
Replies
1
Views
1K
Challenge: Find the minimum amount of draws possible for a list of integers
    • Programming and Computer Science
Replies
9
Views
1K
Are Python strings truly immutable?
    • Programming and Computer Science
Replies
10
Views
2K
MHB Find the context-free grammar,that produces a language
    • Programming and Computer Science
Replies
14
Views
3K
I Using reference frames for derivation of Lagrangian
    • Mechanics
Replies
25
Views
1K
Understanding Ambiguity in If-Else Grammars: An Explanation and Analysis
    • Engineering and Comp Sci Homework Help
Replies
12
Views
2K
Comp Sci Complexity for generating strings of length k from CNF grammar
    • Engineering and Comp Sci Homework Help
Replies
3
Views
945
Von Neumann replicator vehicle model
    • Programming and Computer Science
Replies
23
Views
1K
I Computer languages as examples in formal logic
    • Set Theory, Logic, Probability, Statistics
2
Replies
40
Views
6K
I 'Formulations' of Physical Theories: Overview?
    • Other Physics Topics
Replies
2
Views
13K

Hot Threads

Recent Insights

Back
Top