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 Ll, 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, Ll can provide substantial savings over existing automata inference methods.