Learning DFA for Simple Examples

Parekh, Rajesh G. and Honavar, Vasant G. (1997) Learning DFA for Simple Examples. Technical Report TR97-07, Department of Computer Science, Iowa State University.

Abstract

Learning DFA from Simple Examples
Rajesh Parekh and Vasant Honavar
Abstract:
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 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 examples.  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.


Subjects:
All uncategorized technical reports


ID code:
00000152
Deposited by:
Staff Account on 18 March 1997





Contact site administrator at: ssg@cs.iastate.edu