Language Identification in The Limit - Learnability Characterization

Learnability Characterization

Dana Angluin gave the characterizations of learnability from text (positive information) in her 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).