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

Kousha Etessami, Alistair Stewart, Mihalis Yannakakis

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). T…