The Formal Complexity of Natural Language

Walter J. Savitch (editor), Emmon Bach (editor), William Marsh (editor), Gila Safran-Naveh (editor)9781556080463, 1556080468, 1556080476

Ever since Chomsky laid the framework for a mathematically formal theory of syntax, two classes of formal models have held wide appeal. The finite state model offered simplicity. At the opposite extreme numerous very powerful models, most notable transformational grammar, offered generality. As soon as this mathematical framework was laid, devastating arguments were given by Chomsky and others indicating that the finite state model was woefully inadequate for the syntax of natural language. In response, the completely general transformational grammar model was advanced as a suitable vehicle for capturing the description of natural language syntax. While transformational grammar seems likely to be adequate to the task, many researchers have advanced the argument that it is “too adequate. ” A now classic result of Peters and Ritchie shows that the model of transformational grammar given in Chomsky’s Aspects [IJ is powerful indeed. So powerful as to allow it to describe any recursively enumerable set. In other words it can describe the syntax of any language that is describable by any algorithmic process whatsoever. This situation led many researchers to reasses the claim that natural languages are included in the class of transformational grammar languages. The conclu­ sion that many reached is that the claim is void of content, since, in their view, it says little more than that natural language syntax is doable algo­ rithmically and, in the framework of modern linguistics, psychology or neuroscience, that is axiomatic.

---

Table of contents :
Front Matter….Pages i-xviii
What is Mathematical Linguistics?….Pages 1-18
Front Matter….Pages 19-23
Formal Linguistics and Formal Logic….Pages 24-40
An Elementary Proof of the Peters-Ritchie Theorem….Pages 41-55
On Constraining the Class of Transformational Languages….Pages 56-86
Generative Grammars Without Transformation Rules….Pages 87-116
A Program for Syntax….Pages 117-131
Front Matter….Pages 133-137
Natural Languages and Context-Free Languages….Pages 138-182
Unbounded Dependencies and Coordinate Structure….Pages 183-226
On some Formal Properties of Metarules….Pages 227-250
Some Generalizations of Categorial Grammars….Pages 251-279
Front Matter….Pages 281-285
Cross-Serial Dependencies in Dutch….Pages 286-319
Evidence Against the Context-Freeness of Natural Language….Pages 320-334
English is Not a Context-Free Language….Pages 335-348
The Complexity of the Vocabulary of Bambara….Pages 349-357
Context-Sensitive Grammar and Natural Language Syntax….Pages 358-368
How Non-Context Free is Variable Binding?….Pages 369-386
Computationally Relevant Properties of Natural Languages and Their Grammars….Pages 387-437
Back Matter….Pages 439-451