Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ
Tải xuống
Context-free grammars, far from having insufficient expressive power for the description of human fan K uages, may he overly powerful, along three dimensions; (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 l a n g u a g e s can be a p p r o p r i a t e l y d e s c r i b e d i n terms of a proper subset of the CF-PSG's, namely those with the. | 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 languages may be overly powerful along three dimensions 1 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 misdirected 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 grammars for human languages we need a bit more power than is offered by context-free phrase structure grammars 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 computationally 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 but it can hardly be claimed to be 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. 1. WEAK GENERATIVE CAPACITY Weak generative capacity WGC results are held by some linguists e.g. Chomsky 1981 to be unimportant. Nonetheless they cannot be ignored by linguists who are interested in .
