Rahul Sharma (Editor)

Weighted context free grammar

Updated on
Share on FacebookTweet on TwitterShare on LinkedInShare on Reddit
Covid-19

A weighted context-free grammar (WCFG) is a context-free grammar where each production has a numeric weight associated with it. The weight of a specific parse tree in a WCFG is the product (or sum ) of all rule weights in the tree. Each rule weight is included as often as the rule is used in the tree. A special case of WCFGs are probabilistic context-free grammars (PCFGs), where the weights are (logarithms of ) probabilities.

An extended version of the CYK algorithm can be used to find the "lightest" (least-weight) derivation of a string given some WCFG.

When the tree weight is the product of the rule weights, WCFGs and PCFGs can express the same set of probability distributions.

References

Weighted context-free grammar Wikipedia


Similar Topics
Ek Ajnabee
Ville Ahlgren
Brock Nelson
Topics
 
B
i
Link
H2
L