Evidence against the context-freeness of natural language
Linguistics and PhilosophyPublished 1 August 1985
Stuart M. Shieber
Citations649
SJR quartileQ1
SJR score1.24
SNIP1.63
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
In searching for universal constraints on the class of natural languages, linguists have investigated a number of formal properties, including that of context-freeness, which is interpreted strongly and weakly both as a way of characterizing structure sets and even weakly for characterizing string sets.
Abstract
In searching for universal constraints on the class of natural languages, linguists have investigated a number of formal properties, including that of context-freeness. Soon after Chomsky’s categorization of languages into his well-known hierarchy (Chomsky, 1963), the common conception of the context-free class of languages as a tool for describing natural languages was that it was too restrictive a class — interpreted strongly (as a way of characterizing structure sets) and even weakly (as a way of characterizing string sets).
Keywords
Computer ScienceArts and Humanities
Mathematics and Computers in SimulationIntroduction to automata theory, languages and computation
10,827 Citations1981
Archives of Internal MedicineExperimenter Effects in Behavioral Research.
1,207 Citations1967James L. Titchener
"Clever Hans," the mathematical horse owned by an apparently ingenuous German schoolmaster in the early 1900's, could add, subtract, multiply, divide, read, spell, and solve problems of musical harmony, communicating his answers by tapping his foot.
Cambridge University Press eBooksTree adjoining grammars: How much context-sensitivity is required to provide reasonable structural descriptions?
550 Citations1985Aravind K. Joshi
The Nature of Syntactic Representation
321 Citations1982Pauline Jacobson, Geoffrey K. Pullum
A Semantic Theory of "NP-movement" Dependencies and a Phrase Structure Account of Scandinavian Extraction Phenomena.
Phrase Structure Grammar
257 Citations1982Gerald Gazdar
Studies in linguistics and philosophyNatural Languages and Context-Free Languages
211 Citations1987Geoffrey K. Pullum, Gerald Gazdar
It is shown that every published argument purporting to demonstrate the non-context-freeness of some natural language is invalid, either formally or empirically or both.
Studies in linguistics and philosophyCross-Serial Dependencies in Dutch
189 Citations1982Joan Bresnan, Ronald M. Kaplan +2 more
Chomsky’s argument that natural languages are not finite state languages puts a lower bound on the weak generative capacity of grammars for natural languages (Chomsky (1956), but these arguments are not the only formal considerations by which this can be done.
Proceedings of the 21st annual meeting on Association for Computational Linguistics -
181 Citations1983
This volume provides a record of the proceedings of the 21st Annual Meeting of the Association for Computational Linguistics, held a t the Massachusetts Institute of Technology from 15 to 18 June 1983, and contains both the refereed papers presented at the meeting, and written versions of two of the three invited talks given there.
Studies in linguistics and philosophyThe Complexity of the Vocabulary of Bambara
116 Citations1985Christopher Culy
The weak generative capacity of the vocabulary of Bambara is studied, and it is shown that the vocabulary is not context free.
Studies in linguistics and philosophyEnglish is Not a Context-Free Language
59 Citations1984James Higginbotham
This article exhibits a regular set L, a set that can be generated by a finite-state grammar or accepted by a infinite automaton, whose intersection with English is not a context-free language, and argues that the answer is negative.
On two recent attempts to show that English is not a CFL
27 Citations1984Geoffrey K. Pullum
It has become somewhat more important to linguists to determine at least whether English the most studied language in the era of generative grammar and the primary focus for natural language processing efforts is context-free (CF) or not.
Computational LinguisticsEnglish and the class of context-free languages
19 Citations1984Paul M. Postal, D. Terence Langendoen
Langendoen and Postal (1984) show that for any L, WF(L) is a proper class, hence not a set, much less a recursively enumerable set, and there is thus no question of WF (L) being CF.
Crossed serial dependencies
6 Citations1983Henry S. Thompson
An extension to the GPSG grammatical formalism is proposed, allowing non-terminals to consist of finite sequences of category labels, and allowing schematic variables to range over such sequences, and shown to be parseable by a simple extension to an existing parsing method for GPSG.