Savitch W. The Formal Complexity of Natural Language 1987

Textbook in PDF format

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.
What is Mathematical Linguistics? Stanley Peters
Formal Linguistics and Formal Logic. Janet Dean Fodor
An Elementary Proof of the Peters-Ritchie Theorem. Emmon Bach, William Marsh
On Constraining the Class of Transformational Languages. Thomas Wasow
Generative Grammars Without Transformation Rules. Gilbert H. Harman
A Program for Syntax. P. T. Geach
Natural Languages and Context-Free Languages. Geoffrey K. Pullum, Gerald Gazdar
Unbounded Dependencies and Coordinate Structure. Gerald Gazdar
On some Formal Properties of Metarules. Hans Uszkoreit, Stanley Peters
Some Generalizations of Categorial Grammars. Emmon Bach
Cross-Serial Dependencies in Dutch. Joan Bresnan, Ronald M. Kaplan, Stanley Peters, Annie Zaenen
Evidence Against the Context-Freeness of Natural Language. Stuart M. Shieber
English is Not a Context-Free Language. James Higginbotham
The Complexity of the Vocabulary of Bambara. Christopher Culy
Context-Sensitive Grammar and Natural Language Syntax. Walter J. Savitch
How Non-Context Free is Variable Binding? William Marsh, Barbara H. Partee
Computationally Relevant Properties of Natural Languages and Their Grammars. Gerald Gazdar, Geoffrey K. Pullum