Article,
Probabilistic Languages: A Review and Some Open Questions
ACM Computing Surveys, 12 (4): 361--379 (1980)
DOI: http://doi.acm.org/10.1145/356827.356829
Abstract
Context-free languages are commonly used to describe the structure of programming languages. However many interesting problems involve not just a language's structure but also the actual usage of the language. Adding a notion of probability to ordinary grammars gives rise to probabilistic context-free grammars. Interesting in their own right because of some pretty theorems, probabilistic context-free languages can be applied to the analysis of programming languages, automatic parsers, and error correctors. A complete outline of the theory is presented with examples. Some open questions are posed.
