www.elsevier.com/locate/tcs Minimal cover-automata for "nite languages

A cover-automaton A of a "nite language L⊆ ∗ is a "nite deterministic automaton (DFA) that accepts all words in L and possibly other words that are longer than any word in L. A minimal deterministic "nite cover automaton (DFCA) of a "nite language L usually has a smaller size than a minimal DFA that accept L. Thus, cover automata can be used to reduce the size of the representations of "nite languages in practice. In this paper, we describe an e0cient algorithm that, for a given DFA accepting a "nite language, constructs a minimal deterministic "nite cover-automaton of the language. We also give algorithms for the boolean operations on deterministic cover automata, i.e., on the "nite languages they represent. c © 2001 Elsevier Science B.V. All rights reserved