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 parse tree in a WCFG is the weight of the rule used to produce the top node, plus the weights of its children. A special case of WCFGs are stochastic context-free grammars, 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.
Famous quotes containing the word grammar:
“Like everything metaphysical the harmony between thought and reality is to be found in the grammar of the language.”
—Ludwig Wittgenstein (1889–1951)