We present a framework for learning DFA from simple examples. We show that efficient PAC learning of DFA is possible if the class of distributions is restricted to simple distributions where a teacher might choose examples based on the knowledge of the target concept. This answers an interesting variant of an open research question posed in Pitt's seminal paper: Are DFA's PAC-identifiable if examples are drawn from the uniform distribution, or some other known simple distribution? Our approach uses the RPNI algorithm for learning DFA from labeled exampies. In particular, we describe an efficient learning algorithm for exact learning of the target DFA with high probability when a bound on the number of states (N) of the target DFA is known in advance. When N is not known, we show how this algorithm can be used for efficient PAC learning of DFAs.

Original languageEnglish (US)
Title of host publicationAlgorithmic Learning Theory - 8th International Workshop, ALT 1997, Proceedings
EditorsMing Li, Akira Maruoka
PublisherSpringer Verlag
Number of pages16
ISBN (Print)3540635777, 9783540635772
StatePublished - 1997
Event8th International Workshop on Algorithmic Learning Theory, ALT 1997 - Sendai, Japan
Duration: Oct 6 1997Oct 8 1997

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other8th International Workshop on Algorithmic Learning Theory, ALT 1997

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Learning DFA from simple examples'. Together they form a unique fingerprint.

Cite this