Solution of an Open Problem on Probabilistic Grammars
- 1 August 1983
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. C-32 (8) , 748-750
- https://doi.org/10.1109/tc.1983.1676313
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.Keywords
This publication has 5 references indexed in Scilit:
- Probabilistic Languages: A Review and Some Open QuestionsACM Computing Surveys, 1980
- Inference of Finite-State Probabilistic GrammarsIEEE Transactions on Computers, 1977
- Grammatical Inference: Introduction and Survey - Part IIIEEE Transactions on Systems, Man, and Cybernetics, 1975
- Grammatical Inference: Introduction and Survey - Part IIEEE Transactions on Systems, Man, and Cybernetics, 1975
- Applying Probability Measures to Abstract LanguagesIEEE Transactions on Computers, 1973