http://en.wikipedia.org/wiki/Stochastic_context-free_grammar
A stochastic context-free grammar (SCFG; also probabilistic context-free grammar, PCFG) is a context-free grammar in which each production is augmented with a probability. The probability of a derivation (parse) is then the product of the probabilities of the productions used in that derivation; thus some derivations are more consistent with the stochastic grammar than others.
A variant of the CYK algorithm finds the Viterbi parse of a sequence for a given SCFG. The Viterbi parse is the most likely derivation (parse) of the sequence by the given SCFG.
http://en.wikipedia.org/wiki/CYK_algorithm
The Cocke–Younger–Kasami (CYK) algorithm (alternatively called CKY) determines whether a string can be generated by a given context-free grammar and, if so, how it can be generated. This is known as parsing the string. The algorithm employs bottom-up parsing and dynamic programming.
Chomsky Normal Form
http://en.wikipedia.org/wiki/Chomsky_normal_form
In computer science, a context-free grammar is said to be in Chomsky normal form if all of its production rules are of the form:
A -> BC or
A -> α or
S -> ε
where A, B and C are nonterminal symbols, α is a terminal symbol (a symbol that represents a constant value), S is the start symbol, and ε is the empty string. Also, neither B nor C may be the start symbol.
Every grammar in Chomsky normal form is context-free, and conversely, every context-free grammar can be transformed into an equivalent one which is in Chomsky normal form.
http://en.wikipedia.org/wiki/Weighted_context-free_grammar
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.
No comments:
Post a Comment