Natural languages and the Chomsky hierarchy
András Kornai · 1985
The central claim of the paper is that NL stringsets are regular. Three independent arguments are oered in favor of this position: one based on parsimony considerations, one employing the McCullogh-Pitts (1943) model of neurons, and a purely linguistic one. It is possible to derive explicit upper bounds for the number of (live) states in NL acceptors: the results show that nite state NL parsers can be implemented on presentday computers. The position of NL stringsets within the regular family is also investigated: it is proved that NLs are counter-free, but not locally testable. 0 Introduction The question whether the grammatical sentences of natural languages form regular (Type 3), context free (Type 2), context sensitive (Type 1), or recursively enumerable (Type 0) sets has been subject to much discussion ever since it was posed by Chomsky in his seminal 1956 paper. However, there seems to be little agreement among the linguists concerned with the `geographic' position of natural...