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:
“I went to a very militantly Republican grammar school and, under its influence, began to revolt against the Establishment, on the simple rule of thumb, highly satisfying to a ten-year-old, that Irish equals good, English equals bad.”
—Bernadette Devlin (b. 1947)