Constraining Overgeneration in Formal Grammars

You are reading version 1 of this direction, frozen 2026-10-04. The latest version is version 2.

Version 1 of 234 papers40 conceptsfrozen 2026-10-04

In the quest to teach computers to understand human language, researchers face a persistent "Goldilocks" problem. If a grammar is too simple, it fails to capture the rich complexity of how we speak. But if it is too powerful, it falls into the trap of overgeneration: it begins to accept or produce "linguistic garbage"—sentences that follow mathematical rules but violate the fundamental constraints of human syntax.

The history of computational linguistics is, in many ways, a struggle to find the precise level of restriction that allows for natural expression while strictly forbidding the ungrammatical.

The Paradox of Generative Power

In the early 1980s, the field grappled with the mathematical limits of language. Geoffrey K. Pullum famously argued in Context-Freeness and the Computer Processing of Human Languages that Context-Free Grammars (CFGs) were not only sufficient for natural language but might actually be too powerful. He suggested that human languages belong to a highly restricted subset of these grammars.

When a system is too permissive, it suffers from a lack of "restrictive power." As Eric Wehrli noted in his work on A Modular Parser for French, a parser must be powerful enough to handle language-specific features like clitics or complex verb phrases, yet restrictive enough to reject ungrammatical strings. Without these constraints, the computational burden explodes as the system generates thousands of invalid analyses for a single ambiguous sentence.

Why Grammars Overgenerate

Overgeneration usually occurs when a formal rule is applied too broadly, lacking the "fine print" that governs real-world usage. This happens across several different frameworks:

  1. Combinatory Rules: In Combinatory Categorial Grammar (CCG), powerful operations like type-raising allow for flexible word orders. However, Mark Steedman pointed out in Type-Raising and Directionality in Combinatory Grammar that these same rules can inadvertently allow illegal word permutations, creating a "free word order" problem where none exists.
  2. Logical Unification: When using logic to solve for meaning—such as in ellipsis or focus—researchers often use Higher-Order Unification (HOU). Claire Gardent and Michael Kohlhase demonstrated in Higher-Order Coloured Unification and Natural Language Semantics that HOU is prone to producing a vast number of mathematically sound solutions that no human would ever actually say or understand.
  3. Flexible Word Order: In languages like Hindi, words can move around more freely than in English. Yet, as Alok Debnath and Manish Shrivastava explored in A Pregroup Representation of Word Order Alternation Using Hindi Syntax, if the algebraic transformations intended to allow this "scrambling" aren't strictly bounded, they will validate sequences that disrupt the internal structure of phrases.

The Search for Structural Barriers

To combat this, researchers have moved toward "resource-sensitive" and "constraint-based" models. The goal is to ensure that every syntactic requirement is not just a suggestion, but a debt that must be paid.

Remo Pareschi argued in A Definite Clause Version of Categorial Grammar that overgeneration often happens when a system allows hypothesized elements to be ignored. By treating grammar as a logic where every constituent must be "consumed," we can prevent the system from accepting strings where required roles (like the object of a verb) are missing.

Similarly, Alain Lecomte and Christian Retoré bridged the gap between Chomsky’s Minimalist Program and logic in Extending Lambek Grammars. They showed that by mapping syntactic restrictions directly into a resource-sensitive logic, we can naturally exclude ungrammatical strings that simpler formalisms would let slip through.

Debugging the Permissive Grammar

How do we know if a grammar is too permissive? Traditional parsing only tells us if a system can understand a valid sentence; it doesn't tell us if it also understands nonsense. Claire Gardent addressed this in Generation for Grammar Engineering by introducing GRADE, a tool that uses natural language generation to "stress test" grammars. By forcing a grammar to produce sentences, researchers can see the "dead-end" rules and the ungrammatical output that would otherwise remain hidden in a parser's successful logs.

Ultimately, the research direction suggests that the "intelligence" of a linguistic model isn't just in what it can do, but in what it refuses to do. As Ted Briscoe and Claire Grover emphasized in their work on large-scale English grammars, the challenge of grammar engineering is building rules broad enough to cover the vastness of real-world text while remaining precise enough to maintain the boundaries of human language.

Papers in this version

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 62 papers
  2. Version 1 · 2026-10-04 · 34 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_syntactic_over_generation_434be245,
  title = {syntactic over-generation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/syntactic-over-generation/rdr_434be2450d8e42c480fda194e326416d},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_constraining_overgeneration_in_formal_gr_434be245_v1,
  title = {Constraining Overgeneration in Formal Grammars},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/constraining-overgeneration-in-formal-grammars/rdr_434be2450d8e42c480fda194e326416d/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}