Learning finite cover automata from queries

Learning regular languages from queries was introduced by Angluin in a seminal paper that also provides the L* algorithm. This algorithm, as well as other existing inference methods, finds the exact language accepted by the automaton. However, when only finite languages are used, the construction of a deterministic finite cover automaton (DFCA) is sufficient. A DFCA of a finite language U is a finite automaton that accepts all sequences in U and possibly other sequences that are longer than any sequence in U. This paper presents an algorithm, called L-I, that finds a minimal DFCA of an unknown finite language in polynomial time using membership and language queries, a non-trivial adaptation of Angluin's L* algorithm. As the size of a minimal DFCA of a finite language U may be much smaller than the size of the minimal automaton that accepts exactly U, L-I can provide substantial savings over existing automata inference methods. (C) 2011 Elsevier Inc. All rights reserved.