On stochastic context-free languages

T. Huang; K. S. Fu

doi:10.1016/S0020-0255(71)80007-5

On stochastic context-free languages

T. Huang, K. S. Fu

Coordinated Science Lab

Research output: Contribution to journal › Article › peer-review

Abstract

In this paper, properties of normalized stochastic languages are discussed and alternative procedures for constructing the Chomsky and Greibach normal forms for normalized stochastic context-free grammar (nscfg) are presented. A normalized stochastic context-free language (nscf l) is defined in terms of a nscfg. Furthermore, stochastic languages accepted by stochastic pushdown automata (spda) are defined, and relationships between stochastic context-free languages and spda are studied. The class of languages accepted by a spda with a 0 cutpoint is precisely the class of scf l.

Original language	English (US)
Pages (from-to)	201-224
Number of pages	24
Journal	Information Sciences
Volume	3
Issue number	3
DOIs	https://doi.org/10.1016/S0020-0255(71)80007-5
State	Published - Jul 1971

ASJC Scopus subject areas

Software
Control and Systems Engineering
Theoretical Computer Science
Computer Science Applications
Information Systems and Management
Artificial Intelligence

Online availability

10.1016/S0020-0255(71)80007-5

Library availability

Discover UIUC Full Text

Cite this

@article{ccaf4e67cc0742a4b106a4d606a6f4f2,

title = "On stochastic context-free languages",

abstract = "In this paper, properties of normalized stochastic languages are discussed and alternative procedures for constructing the Chomsky and Greibach normal forms for normalized stochastic context-free grammar (nscfg) are presented. A normalized stochastic context-free language (nscf l) is defined in terms of a nscfg. Furthermore, stochastic languages accepted by stochastic pushdown automata (spda) are defined, and relationships between stochastic context-free languages and spda are studied. The class of languages accepted by a spda with a 0 cutpoint is precisely the class of scf l.",

author = "T. Huang and Fu, {K. S.}",

note = "Funding Information: t This work was supported by National AFOSR grant 69-1776.",

year = "1971",

month = jul,

doi = "10.1016/S0020-0255(71)80007-5",

language = "English (US)",

volume = "3",

pages = "201--224",

journal = "Information Sciences",

issn = "0020-0255",

publisher = "Elsevier Inc.",

number = "3",

}

TY - JOUR

T1 - On stochastic context-free languages

AU - Huang, T.

AU - Fu, K. S.

N1 - Funding Information: t This work was supported by National AFOSR grant 69-1776.

PY - 1971/7

Y1 - 1971/7

N2 - In this paper, properties of normalized stochastic languages are discussed and alternative procedures for constructing the Chomsky and Greibach normal forms for normalized stochastic context-free grammar (nscfg) are presented. A normalized stochastic context-free language (nscf l) is defined in terms of a nscfg. Furthermore, stochastic languages accepted by stochastic pushdown automata (spda) are defined, and relationships between stochastic context-free languages and spda are studied. The class of languages accepted by a spda with a 0 cutpoint is precisely the class of scf l.

AB - In this paper, properties of normalized stochastic languages are discussed and alternative procedures for constructing the Chomsky and Greibach normal forms for normalized stochastic context-free grammar (nscfg) are presented. A normalized stochastic context-free language (nscf l) is defined in terms of a nscfg. Furthermore, stochastic languages accepted by stochastic pushdown automata (spda) are defined, and relationships between stochastic context-free languages and spda are studied. The class of languages accepted by a spda with a 0 cutpoint is precisely the class of scf l.

UR - http://www.scopus.com/inward/record.url?scp=3543007504&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=3543007504&partnerID=8YFLogxK

U2 - 10.1016/S0020-0255(71)80007-5

DO - 10.1016/S0020-0255(71)80007-5

M3 - Article

AN - SCOPUS:3543007504

SN - 0020-0255

VL - 3

SP - 201

EP - 224

JO - Information Sciences

JF - Information Sciences

IS - 3

ER -

On stochastic context-free languages

Abstract

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this