TY - JOUR
T1 - Production probability estimators for context-free grammars
AU - Humenik, Keith
AU - Pinkham, Roger S.
PY - 1990/4
Y1 - 1990/4
N2 - The problem of production probability estimation is considered. We examine the estimation of production probabilities for context-free probabilistic grammars (CFPGs). Given a context-free grammar, G, and a random sample of strings from L(G), we define ratio estimators to estimate the production probabilities of G. It is shown that the statistical analysis of the estimators becomes much less complex by using the theory of random walks. The main result of the article is that the biases and variances of all ratio estimators for any Chomsky Normal Form CFPG are approximately directly proportional to 1 n, where n is the size of the random sample. Random samples consisting of strings generated from an independent source are used to validate theoretical results. We show that the estimates can be used to increase the efficiency of parsing strings in a language. The ability to parse strings efficiently is extremely useful in compiler theory and the theory of artificial intelligence.
AB - The problem of production probability estimation is considered. We examine the estimation of production probabilities for context-free probabilistic grammars (CFPGs). Given a context-free grammar, G, and a random sample of strings from L(G), we define ratio estimators to estimate the production probabilities of G. It is shown that the statistical analysis of the estimators becomes much less complex by using the theory of random walks. The main result of the article is that the biases and variances of all ratio estimators for any Chomsky Normal Form CFPG are approximately directly proportional to 1 n, where n is the size of the random sample. Random samples consisting of strings generated from an independent source are used to validate theoretical results. We show that the estimates can be used to increase the efficiency of parsing strings in a language. The ability to parse strings efficiently is extremely useful in compiler theory and the theory of artificial intelligence.
UR - http://www.scopus.com/inward/record.url?scp=0025417813&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0025417813&partnerID=8YFLogxK
U2 - 10.1016/0164-1212(90)90065-T
DO - 10.1016/0164-1212(90)90065-T
M3 - Article
AN - SCOPUS:0025417813
SN - 0164-1212
VL - 12
SP - 43
EP - 53
JO - The Journal of Systems and Software
JF - The Journal of Systems and Software
IS - 1
ER -