Stochastic Context-Free Grammars, Regular Languages, and Newton’s Method

We study the problem of computing the probability that a given stochastic context-free grammar (SCFG),

G

, generates a string in a given regular language

L

(

D

) (given by a DFA,

D

). This basic problem has a number of applications in statistical natural language processing, and it is also a key necessary step towards quantitative

ω

-regular model checking of stochastic context-free processes (equivalently, 1-exit recursive Markov chains, or stateless probabilistic pushdown processes).

We show that the probability that

G

generates a string in

L

(

D

) can be computed to within arbitrary desired precision in polynomial time (in the standard Turing model of computation), under a rather mild assumption about the SCFG,

G

, and with no extra assumption about

D

. We show that this assumption is satisfied for SCFG’s whose rule probabilities are learned via the well-known inside-outside (EM) algorithm for maximum-likelihood estimation (a standard method for constructing SCFGs in statistical NLP and biological sequence analysis). Thus, for these SCFGs the algorithm always runs in P-time.