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.
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 specification of the class F of functions from which grammars for particular languages may be drawn.
The weakest condition that can significantly be placed on grammars is that F be included in the class of general, unrestricted Turing machines. The strongest, most limiting condition that has been suggested is that each grammar be a finite Markovian source (finite automaton).2
The latter condition is known to be too strong; if F is limited in this way it will not contain a grammar for English (Chomsky, 1956). The former condition, on the other hand, has no interest. We learn nothing about a natural language from the fact that its sentences can be effectively displayed, i.e., that they constitute a reeursively enumerable set. The reason for this is dear. Along with a specification of the class F of grammars, a theory of language must also indicate how, in general, relevant structural information can be obtained for a particular sentence generated by a particular grammar. That is, the theory must specify a class ~ of “structural descriptions” and a functional • such that given f 6 F and x in the range of f, ~(f,x) 6 Z is a structural description of x (with respect to the grammar f) giving certain information which will facilitate and serve as the basis for an account of how x is used and understood by speakers of the language whose grammar is f; i.e., which will indicate whether x is ambiguous, to what other sentences it is structurally similar, etc. These empirical conditions that lead us to characterize F in one way or another are of critical importance. They will not be further discussed in this paper, 3 but it is clear that we will not be able to develop an adequate formulation of ¢ and % if the elements of F are specified only as such “unstructured” devices as general Turing machines.
