A Version Space Approach to Learning Context-free Grammars

Kurt Vanlehn, William Ball

Research output: Contribution to journalArticlepeer-review

26 Scopus citations


In principle, the version space approach can be applied to any induction problem. However, in some cases the representation language for generalizations is so powerful that (1) some of the update functions for the version space are not effectively computable, and (2) the version space contains infinitely many generalizations. The class of context-free grammars is a simple representation that exhibits these problems. This paper presents an algorithm that solves both problems for this domain. Given a sequence of strings, the algorithm incrementally constructs a data structure that has nearly all the beneficial properties of a version space. The algorithm is fast enough to solve small induction problems completely, and it serves as a framework for biases that permit the solution of larger problems heuristically. The same basic approach may be applied to representations that include context-free grammars as special cases, such as And-Or graphs, production systems, and Horn clauses.

Original languageEnglish (US)
Pages (from-to)39-74
Number of pages36
JournalMachine Learning
Issue number1
StatePublished - Mar 1987
Externally publishedYes


  • Induction
  • context-free grammars
  • grammatical inference
  • learning from examples
  • version space

ASJC Scopus subject areas

  • Software
  • Artificial Intelligence


Dive into the research topics of 'A Version Space Approach to Learning Context-free Grammars'. Together they form a unique fingerprint.

Cite this