Stochastic sources for context-free languages
Sandra E. Hutchins · ACM SIGACT News · 1970
The concept of a stochastic source of a context-free language is presented and one possible source model based on a probabilistic grammar is defined. It is shown that this source is equivalent to an infinite Markov chain which can be defined recursively. Various statistics of the Markov chain are derived. An analogue of the Greibach Normal Form theorem is presented, which then allows for the construction of a Markov source with a single terminal symbol per transition. The class of probability distributions generable over context-free languages by such sources is examined.