Context-freeness and the computer processing of human languages
Geoffrey K. Pullum · 1983
Context-free grammars, far from having insufficient expressive power for the description of human fan Kuages, 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 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.