Learning Formal Grammars from Positive Evidence Alone

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

Version 1 of 219 papers24 conceptsfrozen 2026-10-04

How does a child learn the rules of a language without ever being told what is ungrammatical? In formal linguistics and computer science, this is known as the problem of learning from positive evidence. While it seems intuitive that we learn from what we hear, mathematical models of induction suggest that learning a complex grammar from positive examples alone is fundamentally "impossible" without specific constraints.

The Subset Problem and the Danger of Over-generalization

The core difficulty of learning from positive-only data is the subset problem. Imagine a learner trying to identify a target language. If the learner hears the sentences "The cat sat" and "The dog ran," they might hypothesize a restrictive grammar that only allows those specific structures. However, they might also hypothesize a much broader grammar—perhaps one that accepts any sequence of words in any order.

As Moses Charikar and Chirag Pabbaraju note in A Characterization of List Language Identification in the Limit, if a learner makes an overly broad generalization (a "superset" of the true language), they will never encounter a positive example that contradicts their hypothesis. Every valid sentence in the target language is also valid in the over-generalized grammar. Without negative evidence—explicit corrections stating "this sentence is wrong"—the learner has no way to "shrink" their hypothesis back to the correct, smaller language.

This led to E. Mark Gold’s famous 1967 conclusion: most interesting classes of languages (like Context-Free Grammars) cannot be "identified in the limit" from positive data. Binghui Peng, Amin Saberi, and Grigoris Velegkas explain in Language Identification in the Limit with Computational Trace that this occurs because of "limit points"—sequences of nested languages that converge on a larger language, making it impossible for an algorithm to definitively pick the right one.

Solving the Paradox through Structural Constraints

To make language learnable, researchers like Robert C. Berwick argue that the learner must be "pre-programmed" with restrictive, biologically plausible constraints. In Computational Analogues of Constraints on Grammars, Berwick demonstrates that if the search space of possible grammars is sufficiently restricted, a system (like his LPARSIFAL) can acquire syntax using only positive examples.

The "recipe" for learnability involves ensuring that the language class does not contain the kind of nested structures that lead to the subset problem. Several mechanisms have been proposed to achieve this:

  1. Locality and Subregularity: Naoki Abe introduced the concept of "$k$-locality" in Polynominal Learnability and Locality of Formal Grammars, showing that if grammar rules only depend on local context, they become efficiently learnable. Similarly, Jeffrey Heinz in String Extension Learning identifies mathematical properties of "subregular" languages that prevent a learner from assuming an overly broad grammar.
  2. Positive Characteristic Sets: S. Mahmoud Mousawi and Sandra Zilles explore the idea of "characteristic sets"—finite collections of positive examples that are so representative they uniquely identify a language, preventing any learner from jumping to a superset hypothesis (Positive Characteristic Sets for Relational Pattern Languages).
  3. Structured Input: Stefano Crespi-Reghizzi suggested in Reduction of Enumeration in Grammar Acquisition that if the input data is not just a flat string but contains some structural information (like phrases), the number of possible grammars to search through drops dramatically.

Indirect Negative Evidence and Sampling

If the environment doesn't provide explicit negative evidence, perhaps the learner can infer it. Anne Hsu posits in Sampling Assumptions Affect Use of Indirect Negative Evidence in Language Learning that humans are "meta-statistical" learners.

If a learner expects to hear a certain pattern but never does, they eventually treat that absence as indirect negative evidence. However, this only works if the learner assumes the data is a representative sample. If you believe the speaker is providing a random, incomplete set of facts, you won't assume the missing patterns are ungrammatical; you'll just assume they haven't been mentioned yet.

Modern Perspectives: Planning and Traces

Recent work has reframed the acquisition problem using modern computational tools. Javier Segovia-Aguas and colleagues treat grammar induction as a classical planning task (Generating Context-Free Grammars using Classical Planning). By viewing grammar rules as recursive programs, they show that off-the-shelf planners can find the most "efficient" grammar that explains a set of strings, naturally favoring simpler, more accurate models over overly permissive ones.

Furthermore, the success of Large Language Models has prompted a re-evaluation of Gold's pessimism. Peng et al. argue that "Chain-of-Thought" (CoT) processing provides a "computational trace" that makes even the most complex computable languages learnable. By observing the process of derivation rather than just the final string, the learner gains enough information to navigate the subset problem and identify the correct grammar in the limit.

Papers in this version

History & citationVersion 2 · 2026-10-04

Current · Permanent link

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

Latest version (a living page):

@misc{lacuna_limit_point_construction_734383e6,
  title = {limit point construction},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/limit-point-construction/rdr_734383e694f9410f939b50d0753015d0},
  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_learning_formal_grammars_from_positive_e_734383e6_v1,
  title = {Learning Formal Grammars from Positive Evidence Alone},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/learning-formal-grammars-from-positive-evidence-alone/rdr_734383e694f9410f939b50d0753015d0/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}