Minimal Cover-Automata for Finite Languages* Cezar Campeanu,Nicolae Santean,and Sheng Yu Department of Computer Science University of Western Ontario London,Ontario,Canada N6A 5B7 cezar,santean,syu}@csd.uwo.ca Abstract.A cover-automaton A of a finite language L C*is a finite automaton that accepts all words in L and possibly other words that are longer than any word in L.A minimal deterministic cover automaton of a finite 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 finite languages in practice.In this paper,we describe an efficient algorithm that,for a given DFA accepting a finite language,constructs a minimal deterministic finite cover-automaton of the language.We also give algorithms for the boolean operations on deterministic cover automata,i.e.,on the finite languages they represent. 1 Introduction Regular languages and finite automata are widely used in many areas such as lexical analysis,string matching,circuit testing,image compression,and parallel processing.However,many applications of regular languages use actually only finite languages.The number of states of a finite automaton that accepts a finite language is at least one more than the length of the longest word in the language, and can even be in the order of exponential to that number.If we do not restrict an automaton to accept the exact given finite language but allow it to accept extra words that are longer than the longest word in the language,we may obtain an automaton such that the number of states is significantly reduced.In most applications,we know what is the maximum length of the words in the language, and the systems usually keep track of the length of an input word anyway.So, for a finite language,we can use such an automaton plus an integer to check the membership of the language.This is the basic idea behind cover automata for finite languages. Informally,a cover-automaton A of a finite language L is a finite automaton that accepts all words in L and possibly other words that are longer than any word in L.In many cases,a minimal deterministic cover automaton of a finite language L has a much smaller size than a minimal DFA that accept This research is supported by the Natural Sciences and Engineering Research Council of Canada grants OGP0041630. J.-M.Champarnaud,D.Maurel,D.Ziadi (Eds.):WIA'98,LNCS 1660,pp.43-56,1999. C Springer-Verlag Berlin Heidelberg 1999Minimal Cover-Automata for Finite Languages? Cezar Cˆampeanu, Nicolae Sˆantean, and Sheng Yu Department of Computer Science University of Western Ontario London, Ontario, Canada N6A 5B7 {cezar,santean,syu}@csd.uwo.ca Abstract. A cover-automaton A of a finite language L ⊆ Σ∗ is a finite automaton that accepts all words in L and possibly other words that are longer than any word in L. A minimal deterministic cover automaton of a finite 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 finite languages in practice. In this paper, we describe an efficient algorithm that, for a given DFA accepting a finite language, constructs a minimal deterministic finite cover- automaton of the language. We also give algorithms for the boolean operations on deterministic cover automata, i.e., on the finite languages they represent. 1 Introduction Regular languages and finite automata are widely used in many areas such as lexical analysis, string matching, circuit testing, image compression, and parallel processing. However, many applications of regular languages use actually only finite languages. The number of states of a finite automaton that accepts a finite language is at least one more than the length of the longest word in the language, and can even be in the order of exponential to that number. If we do not restrict an automaton to accept the exact given finite language but allow it to accept extra words that are longer than the longest word in the language, we may obtain an automaton such that the number of states is significantly reduced. In most applications, we know what is the maximum length of the words in the language, and the systems usually keep track of the length of an input word anyway. So, for a finite language, we can use such an automaton plus an integer to check the membership of the language. This is the basic idea behind cover automata for finite languages. Informally, a cover-automaton A of a finite language L ⊆ Σ∗ is a finite automaton that accepts all words in L and possibly other words that are longer than any word in L. In many cases, a minimal deterministic cover automaton of a finite language L has a much smaller size than a minimal DFA that accept ? This research is supported by the Natural Sciences and Engineering Research Council of Canada grants OGP0041630. J.-M. Champarnaud, D. Maurel, D. Ziadi (Eds.): WIA’98, LNCS 1660, pp. 43–56, 1999. c Springer-Verlag Berlin Heidelberg 1999