Language identification in the limit

Language identification in the limit is a formal model for inductive inference. It was introduced by E. Mark Gold in his paper with the same title In this model, a learner is provided with presentation (i.e. strings) of some formal language. The learning is seen as an infinite process. Each time an element of the presentation is read the learner should provide a representation (e.g. a formal grammar) for the language. It is said that a learner can identify in the limit a class of languages if given any presentation of any language in the class the learner will produce only a finite number of wrong representations, and therefore converge on the correct representation in a finite number of steps, without however necessarily being able to announce its correctness since a counterexample to that representation could appear as an element arbitrarily long after.

Gold defined two types of presentations:

This model is an early attempt to formally capture the notion of learnability. Gold's paper introduces for contrast the stronger models

A weaker formal model of learnability is the Probably approximately correct learning (PAC) model, introduced by Leslie Valiant in 1984.

It is instructive to look at concrete examples (in the tables) of learning sessions the definition of identification in the limit speaks about.

Dana Angluin gave the characterizations of learnability from text (positive information) in a 1980 paper. If a learner is required to be effective, then an indexed class of recursive languages is learnable in the limit if there is an effective procedure that uniformly enumerates tell-tales for each language in the class (Condition 1). It is not hard to see that if we allow an ideal learner (i.e., an arbitrary function), then an indexed class of languages is learnable in the limit if each language in the class has a tell-tale (Condition 2).

The table shows which language classes are identifiable in the limit in which learning model. On the right-hand side, each language class is a superclass of all lower classes. Each learning model (i.e. type of presentation) can identify in the limit all classes below it. In particular, the class of finite languages is identifiable in the limit by text presentation (cf. Example 2 above), while the class of regular languages is not.

...
Wikipedia