--- title: "English and the Class of Context-Free Languages — Postal 1984" description: "Its method is a formal proof built on sluicing, as in sentences like \"someone left, but I don't know who.\"… 11 references, cited by 4 papers here." authors: ["Paul M. Postal", "D. Terence Langendoen"] year: 1984 venue: "Computational Linguistics" source: "https://aclanthology.org/J84-3002/" licence: "CC BY-NC-SA 3.0 (ACL Anthology, before 2016)" licence_url: "https://creativecommons.org/licenses/by-nc-sa/3.0/" summary_licence: "Elamur Cosmic License" canonical: "https://research.elamur.ai/free/en/papers/postal-1984-english-class-context-free-languages/" --- [Elamur Research](https://md.research.elamur.ai/free/en/) · [this page in HTML](https://research.elamur.ai/free/en/papers/postal-1984-english-class-context-free-languages/) [home](https://md.research.elamur.ai/free/en/) / [papers](https://md.research.elamur.ai/free/en/papers/) / [1984](https://md.research.elamur.ai/free/en/papers/1984/) / English and the Class of Context-Free Languages # English and the Class of Context-Free Languages **Authors:** Paul M. Postal and D. Terence Langendoen · **Year:** 1984 · **Venue:** [Computational Linguistics](https://md.research.elamur.ai/free/en/venues/cl/) ([Computational Linguistics 1984](https://md.research.elamur.ai/free/en/venues/cl/1984/)) · **Licence:** [CC BY-NC-SA 3.0 (ACL Anthology, before 2016)](https://creativecommons.org/licenses/by-nc-sa/3.0/) **Links:** [Publisher's page](https://aclanthology.org/J84-3002/) · [PDF](https://aclanthology.org/J84-3002.pdf) · [OpenAlex](https://openalex.org/W1550226055) **Citations:** 19 citations (OpenAlex, 2026-10-14) · 4 in our library, of the 149,439 papers whose bibliographies we read ## Summary The paper asks whether the finite well-formed sentences of English form a context-free (CF) stringset. Pullum and Gazdar (1982) had shown that every earlier non-CF argument failed. The authors' own 1984 result made full natural languages proper classes, because they contain transfinite sentences, but it said nothing about the finite part. The paper uses no corpus or treebank. Its method is a formal proof built on sluicing, as in sentences like "someone left, but I don't know who." The authors describe two dialects. In E1, a strong matching condition requires the wh-nominal to repeat the antecedent up to its head noun. In E2, a weak condition accepts any possible anaphor, such as a synonym or a broader term. For nested agentive compounds like "bourbon hater lover", both conditions demand exact repetition. Intersecting English with a regular set of such sluices therefore yields a copying language, which is not CF. By an intersection corollary of Arbib's theorem, English is not CF either. This settles a long-disputed question. It also suggests that indexed grammars may be powerful enough for the finite part of English. ## Key points - The proof relies on two facts. First, if L ∩ R is non-CF for a regular set R, then L is non-CF (a corollary of Arbib 1969). Second, copying languages {cxdxe | x ∈ {a,b}*} are non-CF (Langendoen 1977). - The regular filter R consists of sluices in which "Joe discussed some bourbon" is followed by a string x, then "but WHICH bourbon", then a string y, and finally "is unknown", with x and y ranging over {hater, lover}*. The matching condition forces x = y, which turns the intersection into a copying language. - The data are restricted to cases with: - phrasal stress on the wh-quantifier, which gives the anaphoric reading; - non-empty, non-pronominal nominals; - only overt antecedents, so cases like "Max discussed Tom but… who" are excluded. - The two dialects differ on some cases: - E1 rejects "how many machines" referring back to "typewriters". - Both dialects reject sibling or narrower terms ("nurses" for "physicians", "equations" for "formulas"). - Both reject an exocentric head ("escape" for "fire escape"). - The authors conclude that FWF(English) is not CF, but nothing yet places it outside the indexed languages (Aho 1968). A theory that combines proper-class languages with an indexed finite part remains to be built. ## Interesting ideas - Restricting the vocabulary can make intensionally different rules (here, the two dialects' matching conditions) extensionally identical, so a single result covers every variant at once. - A sluiced wh-phrase is interpreted as a whole clause: the first clause with the indefinite removed and the wh-word put in its place. - In E2, an anaphoric nominal may be identical, synonymous, or more general than its antecedent, but never narrower or a sibling. This is a grammatical constraint that holds even when context makes the terms interchangeable. - A compound's head can stand in for the whole compound only when the compound is endocentric, that is, a kind of its head ("candy store" is a store; "fire escape" is not an escape). - Intersecting a language with a simple regular template isolates one dependency pattern cleanly enough to test it. ## For Mova How these ideas could serve Mova, our small open language model — its files, stages and tests: - **I1** (learn): build evaluation suites over a controlled vocabulary where annotation or dialect differences vanish, so disagreements between witness parsers point to real errors rather than convention. - **I2** (frames): resolve sluices by copying the antecedent clause's frame, then filling the role of the indefinite ("something") with the wh-question. "it's not known what" then becomes an explicit question frame over "he stole _". - **I3** (frames): use WordNet hypernymy as a hard filter when linking definite or wh-nominals to antecedents, rejecting hyponym and co-hyponym links regardless of context. - **I4** (world): mark compounds in the ontology as endocentric or exocentric. Entity linking then allows "the store" to refer back to "candy store" but blocks "escape" from referring back to "fire escape". - **I5** (learn): use regular sentence templates with copying slots to generate probe sets. These check whether the parser and coreference module actually enforce identity between distant spans rather than guessing locally. *Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.* ## Institutions - [IBM Research - Thomas J. Watson Research Center](https://md.research.elamur.ai/free/en/labs/ibm-research-thomas-j-watson-research-center/) — Research institute, Yorktown Heights, United States · 53 works · 49,193 citations - [City University of New York](https://md.research.elamur.ai/free/en/universities/city-university-of-new-york/) — University, New York, United States · 17 works · 2,564 citations 📚 Shelves (6): [🖥️ Computer Science](https://md.research.elamur.ai/free/en/shelves/computer-science/) · 16,667 works · [🎭 Arts and Humanities](https://md.research.elamur.ai/free/en/shelves/arts-and-humanities/) · 16,039 works · [🗣️ Language and Linguistics](https://md.research.elamur.ai/free/en/shelves/arts-and-humanities/language-and-linguistics/) · 15,891 works · [💭 Psychology](https://md.research.elamur.ai/free/en/shelves/psychology/) · 1,552 works · [🧮 Computational Theory and Mathematics](https://md.research.elamur.ai/free/en/shelves/computer-science/computational-theory-and-mathematics/) · 252 works · [💭 Developmental and Educational Psychology](https://md.research.elamur.ai/free/en/shelves/psychology/developmental-and-educational-psychology/) · 499 works 🧭 Topics (1): [English](https://md.research.elamur.ai/free/en/topics/english/) · 2,263 works ## Cite Cite as: Paul M. Postal and D. Terence Langendoen. 1984. English and the Class of Context-Free Languages. Computational Linguistics. The paper itself, not this page. BibTeX from the library's record of the work. ```bibtex @article{postal1984english, title = {{English and the Class of Context-Free Languages}}, author = {Paul M. Postal and D. Terence Langendoen}, journal = {Computational Linguistics}, year = {1984}, doi = {10.5555/970170.970172}, url = {https://doi.org/10.5555/970170.970172} } ``` - [next → The grammatical tagging of unrestricted English text](https://md.research.elamur.ai/free/en/papers/garside-1984-grammatical-tagging-unrestricted-english-text/) - [↑ back to papers of 1984](https://md.research.elamur.ai/free/en/papers/1984/) ## References 11 references, 0 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet. 1. Aho, A.V. 1968 Indexed Grammars-An Extension of Context-Free Grammars, Journal of the Association for Computing Machinery 15: 647-671. [find](https://scholar.google.com/scholar?q=Aho%2C+A%2EV%2E+1968+Indexed+Grammars%2DAn+Extension+of+Context%2DFree+Grammars%2C+Journal+of+the+Association+for+Computing+Machinery+15%3A+647%2D671%2E) 2. Arbib, M. 1969 Theories of Abstract Automata. Prentice-Hall, Englewood Cliffs, New Jersey. [find](https://scholar.google.com/scholar?q=Arbib%2C+M%2E+1969+Theories+of+Abstract+Automata%2E+Prentice%2DHall%2C+Englewood+Cliffs%2C+New+Jersey%2E) 3. Daly, R.T. 1974 Applications of the Mathematical Theory of Linguistics. Mouton and Company, The Hague. [↗](https://doi.org/10.1515/9783110908572) 4. Gazdar, G. 1983 NLs, CFLs and CF-PSGs. In: Sparck Jones, K. and Wilks, Y., Eds., Automatic Natural Language Parsing. Ellis Horwood Ltd., West Sussex, England. [find](https://scholar.google.com/scholar?q=Gazdar%2C+G%2E+1983+NLs%2C+CFLs+and+CF%2DPSGs%2E+In%3A+Sparck+Jones%2C+K%2E+and+Wilks%2C+Y%2E%2C+Eds%2E%2C+Automatic+Natural+Language+Parsing%2E+Ellis+Horwood+Ltd%2E%2C+West+Sussex%2C+England%2E) 5. Higginbotham, J. 1984 English is Not a Context-Free Language. Linguistic Inquiry 15:119-126. [↗](https://doi.org/10.1007/978-94-009-3401-6_13) 6. Langendoen, D.T. 1977 On the Inadequacy of Type-2 and Type-3 Grammars for'Human Languages. In: Hopper, P.J., Ed., Studies in Descriptive and Historical Lingistics. John Benjamins, Amsterdam, Holland. [find](https://scholar.google.com/scholar?q=Langendoen%2C+D%2ET%2E+1977+On+the+Inadequacy+of+Type%2D2+and+Type%2D3+Grammars+for%27Human+Languages%2E+In%3A+Hopper%2C+P%2EJ%2E%2C+Ed%2E%2C+Studies+in+Descriptive+and+Historical+Lingistics%2E+John+Benjamins%2C+Amsterdam%2C+Holland%2E) 7. Langendoen, D.T. and Postal, P.M. 1984 The Vastness of Natural Languages. Basil Blackwell, Oxford, England. [find](https://scholar.google.com/scholar?q=Langendoen%2C+D%2ET%2E+and+Postal%2C+P%2EM%2E+1984+The+Vastness+of+Natural+Languages%2E+Basil+Blackwell%2C+Oxford%2C+England%2E) 8. Levin, L. 1982 Sluicing: A Lexical Interpretation Procedure. In: Bresnan, J., Ed., The Mental Representation of Grammatical Relations. The M1T Press, Cambridge, Massachusetts. [find](https://scholar.google.com/scholar?q=Levin%2C+L%2E+1982+Sluicing%3A+A+Lexical+Interpretation+Procedure%2E+In%3A+Bresnan%2C+J%2E%2C+Ed%2E%2C+The+Mental+Representation+of+Grammatical+Relations%2E+The+M1T+Press%2C+Cambridge%2C+Massachusetts%2E) 9. Pullum, G.K. and Gazdar, G. 1982 Natural Languages and Context-Free Languages: Linguistics and Philosophy 4:471-504. [find](https://scholar.google.com/scholar?q=Pullum%2C+G%2EK%2E+and+Gazdar%2C+G%2E+1982+Natural+Languages+and+Context%2DFree+Languages%3A+Linguistics+and+Philosophy+4%3A471%2D504%2E) 10. Ross, J. R. 1969 Guess Who. In: Binnick, R. et al., Eds., Papers from the Fifth Regional Meeting Chicago Linguistic Society. University of Chicago, Chicago, Illinois. [find](https://scholar.google.com/scholar?q=Ross%2C+J%2E+R%2E+1969+Guess+Who%2E+In%3A+Binnick%2C+R%2E+et+al%2E%2C+Eds%2E%2C+Papers+from+the+Fifth+Regional+Meeting+Chicago+Linguistic+Society%2E+University+of+Chicago%2C+Chicago%2C+Illinois%2E) 11. van Riemsdyk, H. 1978 ,4 Case Study in Syntactic Markedness: The Binding Nature of Prepositional Phrases. Foris Publications, Dordrecht, Holland. [find](https://scholar.google.com/scholar?q=van+Riemsdyk%2C+H%2E+1978+%2C4+Case+Study+in+Syntactic+Markedness%3A+The+Binding+Nature+of+Prepositional+Phrases%2E+Foris+Publications%2C+Dordrecht%2C+Holland%2E) *Updated 1 November 2026*