Title
Solution of an open problem on probabilistic grammars
Document Type
Article
Publication Date
1983
Department/School
Computer Science
Abstract
It has been proved that when the production probabilities of an unambiguous context-free grammar G are estimated by the relative frequencies of the corresponding productions in a sample S from the language L(G) generated by G, the expected derivation length and the expected word length of the words in L(G) are precisely equal to the mean derivation length and the mean world length of the words in the same S, respectively.
Link to Published Version
Recommended Citation
Chaudhuri, R., Pham, S., & Garcia, O. N. (1983). Solution of an open problem on probabilistic grammars. IEEE Transactions on Computers, C-32(8), 748–750. doi:10.1109/TC.1983.1676313