Learning regular sets from queries and counterexamples. (English) Zbl 0636.68112

Summary: The problem of identifying an unknown regular set from examples of its members and nonmembers is addressed. It is assumed that the regular set is presented by a minimally adequate Teacher, which can answer membership queries about the set and can also test a conjecture and indicate whether it is equal to the unknown set and provide a counterexample if not. (A counterexample is a string in the symmetric difference of the correct set and the conjectured set.) A learning algorithm L* is described that correctly learns any regular set from any minimally adequate Teacher in time polynomial in the number of states of the minimum dfa for the set and the maximum length of any counterexample provided by the Teacher. It is shown that in a stochastic setting the ability of the Teacher to test conjectures may be replaced by a random sampling oracle, EX( ). A polynomial-time learning algorithm is shown for a particular problem of context-free language identification.


68T05 Learning and adaptive systems in artificial intelligence
Full Text: DOI


[1] Angluin, D., A note on the number of queries needed to identify regular languages, Inform. Contr., 51, 76-87 (1982) · Zbl 0504.68050
[2] Angluin, D.; Smith, C., Inductive inference: Theory and methods, Comput. Surveys, 15, 237-269 (1983)
[3] Blumer, A.; Ehrenfeucht, A.; Haussler, D.; Warmuth, M., Classifying learnable geometric concepts with the Vapnik-Chervonenkis dimension, (Proceedings, Eighteenth Annual ACM Symposium on Theory of Computing (1986), Assoc. Comput. Mach: Assoc. Comput. Mach New York), 273-282
[4] Gold, E. M., Complexity of automaton identification from given data, Inform. Contr., 37, 302-320 (1978) · Zbl 0376.68041
[5] Gold, E. M., System identification via state characterization, Automatica, 8, 621-636 (1972) · Zbl 0251.93008
[6] Jones, N. D.; Laaser, W. T., Complete problems for deterministic polynomial time, Theoret. Comput. Sci., 3, 107-113 (1977)
[7] Shapiro, E., Algorithmic Program Debugging, (Ph.D. thesis (1982), Yale University Computer Science Dept), (1983), published by MIT Press, Cambridge, MA
[8] Valiant, L. G., A theory of the learnable, Comm. ACM, 27, 1134-1142 (1984) · Zbl 0587.68077
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.