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.
Description
Probabilistic Languages: A Review and Some Open Questions
%0 Journal Article
%1 Wetherell1980
%A Wetherell, Charles Stanley
%C New York, NY, USA
%D 1980
%I ACM
%J ACM Computing Surveys
%K grammar probabilisticgrammar
%N 4
%P 361--379
%R http://doi.acm.org/10.1145/356827.356829
%T Probabilistic Languages: A Review and Some Open Questions
%U http://portal.acm.org/citation.cfm?id=356827.356829
%V 12
%X 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.
@article{Wetherell1980,
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.},
added-at = {2009-11-16T15:18:06.000+0100},
address = {New York, NY, USA},
author = {Wetherell, Charles Stanley},
biburl = {https://www.bibsonomy.org/bibtex/24959ce15bf4947c142cd256fbdc84e6c/tmalsburg},
description = {Probabilistic Languages: A Review and Some Open Questions},
doi = {http://doi.acm.org/10.1145/356827.356829},
interhash = {950e500c4a0b801c93c1b4c8fd8868c5},
intrahash = {4959ce15bf4947c142cd256fbdc84e6c},
issn = {0360-0300},
journal = {ACM Computing Surveys},
keywords = {grammar probabilisticgrammar},
number = 4,
pages = {361--379},
publisher = {ACM},
timestamp = {2009-11-16T15:18:06.000+0100},
title = {Probabilistic Languages: A Review and Some Open Questions},
url = {http://portal.acm.org/citation.cfm?id=356827.356829},
volume = 12,
year = 1980
}