Context-Freeness and the Computer Processing of Human Languages

CONTEXT-FREENESS AND THE COMPUTER PROCESSING OF HUMAN LANGUAGES Geoffrey K. Pullum Cowell College University of California, Santa Cruz Santa Cruz, California 95064 ABSTRACT Context-free grammars, far from having insufficient expressive power for the description of human fan K - uages, may he overly powerful, along three dimen- sions; (i) weak generative capacity: there exists an interesting proper subset of the CFL's, the profligate CFL's, within which no human language appears to fall; (2) strong generative capacity: human languages can be appropriately described in terms of a proper subset of the CF-PSG's, namely those with the ECPO property; (3) time complexity: the recent controversy about the importance of a low deterministic polynomial time bound on the recognition problem for human languages is mis- directed, since an appropriately restrictive theory would guarantee even more, namely a linear bound. 0. INTRODUCTION Many computationally inclined linguists appear to think that in order to achieve adequate gr~----rs for human languages we need a hit more power than is offered by context-free phrase structure gram- mars (CF-PSG's), though not a whole lot more. In this paper, I am concerned with the defense of a more conservative view: that even CF-PSG's should be regarded as too powerful, in three computation- ally relevant respects: weak generative capacity, strong generative capacity, and time complexity of recognition. All three of these matters should be of concern to theoretical linguists; the study of what mathematically definable classes human languages fall into does not exhaust scientific linguistics, hut it can hardly he claimed to he irrelevant to it. And it should be obvious that all three issues also have some payoff in terms of certain computationally interesting, if rather indirect, implications. I. WEAK GENERATIVE CAPACITY Weak generative capacity (WGC) results are held by some linguists (e.g. Chomsky (1981)) to be unim- portant. Nonetheless, they cannot be ignored by linguists who are interested in setting their work in a context of (even potential) computational implementation (which, of course, some linguists are not). To paraphrase Montague, we might say that linguistically (as opposed to psycholinguisti- cally) there is no important theoretical difference between natural languages and high-level program- ming languages. Mediating programs (e.g. a com- piler or interpreter), of considerable complexity, will be needed for the interpretation of computer input in either Prolog or Japanese. In the latter case the level of complexity will be much higher, but the assumption is that we are talking quantita- tively, not qualitatively. And if we are seriously interested in the computational properties of either kind of language, we will be interested in their language-theoretic properties, as well as properties of the grammars that define them and the parsers that accept them. The most important language-theoretic class con- sidered by designers of programming languages, com- pilers, etc. is the context-free languages (CFL's). Ginsburg (1980, 7) goes so far as to say on behalf of formal language theorists, "We live or die on the context-free languages.") The class of CFL's is very rich. Although there are simply definable languages …

Content truncated to 500 words