Stochastic grammars and languages

K. S. Fu, Thomas S Huang

Research output: Contribution to journalArticle

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 languageEnglish (US)
Pages (from-to)135-170
Number of pages36
JournalInternational Journal of Computer & Information Sciences
Volume1
Issue number2
DOIs
StatePublished - Jun 1 1972
Externally publishedYes

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computational Theory and Mathematics

Fingerprint Dive into the research topics of 'Stochastic grammars and languages'. Together they form a unique fingerprint.

  • Cite this