Weighted contextfree grammar
From Infogalactic: the planetary knowledge core
It has been suggested that this article be merged with Stochastic contextfree grammar. (Discuss) Proposed since February 2015.

A weighted contextfree grammar (WCFG) is a contextfree grammar where each production has a numeric weight associated with it. The weight of a specific parse tree in a WCFG is the product^{[1]} (or sum^{[2]} ) 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 contextfree grammars (PCFGs), where the weights are (logarithms of ^{[3]}^{[4]}) probabilities.
An extended version of the CYK algorithm can be used to find the "lightest" (leastweight) 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.^{[1]}
References
 ↑ ^{1.0} ^{1.1} Smith, Noah A.; Johnson, Mark (2007). "Weighted and Probabilistic ContextFree Grammars Are Equally Expressive". Computational Linguistics. 33 (4): 477. doi:10.1162/coli.2007.33.4.477.<templatestyles src="Module:Citation/CS1/styles.css"></templatestyles>
 ↑ Katsirelos, George; Narodytska, Nina; Walsh, Toby (2008). "The Weighted Cfg Constraint". Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems. Lecture Notes in Computer Science. 5015. p. 323. doi:10.1007/9783540681557_31. ISBN 9783540681540.<templatestyles src="Module:Citation/CS1/styles.css"></templatestyles>
 ↑ Johnson, Mark (2005). "log linear or Gibbs models" (PDF).<templatestyles src="Module:Citation/CS1/styles.css"></templatestyles>
 ↑ Chi, Zhiyi (March 1999). "Statistical properties of probabilistic contextfree grammars" (PDF). Computational Linguistics. 25 (1): 131–160.<templatestyles src="Module:Citation/CS1/styles.css"></templatestyles>
This syntaxrelated article is a stub. You can help Infogalactic by expanding it. 
P ≟ NP  This theoretical computer science–related article is a stub. You can help Infogalactic by expanding it. 