TY - JOUR

T1 - On certain formal properties of grammars

AU - Chomsky, Noam

N1 - Funding Information:
A language is a collection of sentences of finite length all constructed from a finite alphabet (or, where our concern is limited to syntax, a finite vocabulary) of symbols. Since any language L in which we are likely to be interested is an infinite set, we can investigate the structure of L only through the study of the finite devices (grammars) which are capable of enumerating its sentences. A grammar of L can be regarded as a function whose range is exactly L. Such devices have been called "sentence-generating grammars. ''z A theory of language will contain, then, a specifica- * This work was supported in part by the U. S. Army (Signal Corps), the U. S. Air Force (Office of Scientific Research, Air Research and Development Command), and the U. S. Navy (Office of Naval Research). This work was also supported in part by the Transformations Project on Information Retrieval of the University of Pennsylvania. I am indebted to George A. Miller for several important observations about the systems under consideration here, and to I~. B. Lees for material improvements in presentation. i Following a familiar technical use of the term "generate," cf. Post (1944). This locution has, however, been misleading, since it has erroneously been interpreted as indicating that such sentence-generating grammars consider language

PY - 1959/6

Y1 - 1959/6

N2 - A grammar can be regarded as a device that enumerates the sentences of a language. We study a sequence of restrictions that limit grammars first to Turing machines, then to two types of system from which a phrase structure description of the generated language can be drawn, and finally to finite state Markov sources (finite automata). These restrictions are shown to be increasingly heavy in the sense that the languages that can be generated by grammars meeting a given restriction constitute a proper subset of those that can be generated by grammars meeting the preceding restriction. Various formulations of phrase structure description are considered, and the source of their excess generative power over finite state sources is investigated in greater detail.

AB - A grammar can be regarded as a device that enumerates the sentences of a language. We study a sequence of restrictions that limit grammars first to Turing machines, then to two types of system from which a phrase structure description of the generated language can be drawn, and finally to finite state Markov sources (finite automata). These restrictions are shown to be increasingly heavy in the sense that the languages that can be generated by grammars meeting a given restriction constitute a proper subset of those that can be generated by grammars meeting the preceding restriction. Various formulations of phrase structure description are considered, and the source of their excess generative power over finite state sources is investigated in greater detail.

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

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

U2 - 10.1016/S0019-9958(59)90362-6

DO - 10.1016/S0019-9958(59)90362-6

M3 - Article

AN - SCOPUS:49749213366

VL - 2

SP - 137

EP - 167

JO - Information and Computation

JF - Information and Computation

SN - 0890-5401

IS - 2

ER -