The Halting Problem for Probabilistic Context-Free Generators
Clarence A. Ellis · Journal of the ACM · 1972
A computer program which randomly generates strings of a language from a phrase structure grammar is considered.By developing a theory of probabilistic languages and probabilistic grammars, a necessary and sufficient condition for the program to stop with probability one is established.