Abstract
This paper summarizes some recent results concerned with the extension of formal languages to their corresponding stochastic versions. Weighted grammars and languages are first defined, and stochastic grammars and languages are defined as a special case of weighted grammars and languages. Fuzzy grammars and languages, which have some properties similar to weighted grammars and languages, are also discussed. Stochastic automata are defined from the language recognition viewpoint. Languages accepted by stochastic finite-state and pushdown automata, with and without a cutpoint, are studied. Weighted and stochastic programmed and indexed grammars, and stochastic nested stack automata are defined. Finally, some decidability problems of stochastic (weighted, fuzzy) languages are discussed, and problems for further research are suggested.
| Original language | English (US) |
|---|---|
| Pages (from-to) | 135-170 |
| Number of pages | 36 |
| Journal | International Journal of Computer & Information Sciences |
| Volume | 1 |
| Issue number | 2 |
| DOIs | |
| State | Published - Jun 1972 |
| Externally published | Yes |
ASJC Scopus subject areas
- Theoretical Computer Science
- Computational Theory and Mathematics