Minimal Cover-Automata for Finite Languages.pdf_大学文库

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 1999

Minimal 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

44 Cezar Campeanu,Nicolae Santean,and Sheng Yu L.Thus,cover automata can be used to reduce the size of automata for finite languages in practice. Intuitively,a finite automaton that accepts a finite language (exactly)can be viewed as having structures for the following two functionalities: 1.checking the patterns of the words in the language,and 2.controlling the lengths of the words. In a high-level programming language environment,the length-control function is much easier to implement by counting with an integer than by using the structures of an automaton.Furthermore,the system usually does the length- counting anyway.Therefore,a DFA accepting a finite language may leave out the structures for the length-control function and,thus,reduce its complexity. The concept of cover automata is not totally new.Similar concepts have been studied in different contexts and for different purposes.See,for example, [1,7,4,10.Most of previous work has been in the study of a descriptive complexity measure of arbitrary languages,which is called "automaticity"by Shallit et al. [10.In our study,we consider cover automata as an implementing method that may reduce the size of the automata that represent finite languages. In this paper,as our main result,we give an efficient algorithm that,for a given finite language (given as a deterministic finite automaton or a cover automaton),constructs a minimal cover automaton for the language.Note that for a given finite language,there might be several minimal cover automata that are not equivalent under a morphism.We will show that,however,they all have the same number of states. 2 Preliminaries Let T be a set.Then by #T we mean the cardinality of T.The elements of T* are called strings or words.The empty string is denoted by A.If w E T*then w is the length of z. We define Tl=wETI=1),TsI=UTi,and T0,the quasi-lexicographical order on T*,denoted <is defined by:x<y iff<ly orzl=ly and x=ztv,y=ztu,i<j,for some z,u,v∈T*and1≤i,j≤k. Denote x<y if x<y or =y. We say that x is a prefix of y,denoted xpy,if y=xz for some zET. A deterministic finite automaton (DFA)is a quintuple A=(,Q,qo,6,F), where and Q are finite nonempty sets,qo∈Q,FCQ and6:Q×D-→Q is the transition function.We can extend 6 from Qx to Qx by (s,)=s (s,aw)=(6(s,a),w). We usually denote 6 by 6

44 Cezar Cˆampeanu, Nicolae Sˆantean, and Sheng Yu L. Thus, cover automata can be used to reduce the size of automata for finite languages in practice. Intuitively, a finite automaton that accepts a finite language (exactly) can be viewed as having structures for the following two functionalities: 1. checking the patterns of the words in the language, and 2. controlling the lengths of the words. In a high-level programming language environment, the length-control function is much easier to implement by counting with an integer than by using the structures of an automaton. Furthermore, the system usually does the lengthcounting anyway. Therefore, a DFA accepting a finite language may leave out the structures for the length-control function and, thus, reduce its complexity. The concept of cover automata is not totally new. Similar concepts have been studied in different contexts and for different purposes. See, for example, [1,7,4,10]. Most of previous work has been in the study of a descriptive complexity measure of arbitrary languages, which is called “automaticity” by Shallit et al. [10]. In our study, we consider cover automata as an implementing method that may reduce the size of the automata that represent finite languages. In this paper, as our main result, we give an efficient algorithm that, for a given finite language (given as a deterministic finite automaton or a cover automaton), constructs a minimal cover automaton for the language. Note that for a given finite language, there might be several minimal cover automata that are not equivalent under a morphism. We will show that, however, they all have the same number of states. 2 Preliminaries Let T be a set. Then by #T we mean the cardinality of T . The elements of T ∗ are called strings or words. The empty string is denoted by λ. If w ∈ T ∗ then |w| is the length of x. We define T l = {w ∈ T ∗ | |w| = l}, T ≤l = [ l i=0 T i , and T 0, the quasi-lexicographical order on T ∗, denoted ≺, is defined by: x ≺ y iff |x| < |y| or |x| = |y| and x = ztiv, y = ztju, i<j, for some z, u, v ∈ T ∗ and 1 ≤ i, j ≤ k. Denote x y if x ≺ y or x = y. We say that x is a prefix of y, denoted x p y, if y = xz for some z ∈ T . A deterministic finite automaton (DFA) is a quintuple A = (Σ, Q, q0, δ, F), where Σ and Q are finite nonempty sets, q0 ∈ Q, F ⊆ Q and δ : Q × Σ −→ Q is the transition function. We can extend δ from Q × Σ to Q × Σ∗ by δ(s, λ) = s δ(s, aw) = δ(δ(s, a), w). We usually denote δ by δ

Minimal Cover-Automata for Finite Languages 45 The language recognised by the automaton A is L(A)={w∈∑*|6(go,w)∈ F}.For simplicity,we assume that Q={0,1,...,#Q-1}and go =0.In what follows we assume that 6 is a total function,i.e.,the automaton is complete. Let l be the length of the longest word(s)in the finite language L.A DFA A such that L(A)st=L is called a deterministic finite cover-automaton (DFCA)of L.Let A=(Q,6,0,F)be a DFCA of a finite language L.We say that A is a minimal DFCA of L if for every DFCA B=(Q',∑，6'，0，F')ofL we have#Q≤#Q'. LetA=(Q,∑，d,0,F)be a DFA.Then a)geQ is said to be accessible if there exists w such that 6(0,w)=g, b)g is said to be useful (coaccessible)if there exists wE*such that 6(q,w)∈F. It is clear that for every DFA A there exists an automaton A'such that L(A')= L(A)and all the states of A'are accessible and at most one of the states is not useful (the sink state).The DFA A'is called a reduced DFA. In what follows we shall use only reduced DFA. 3 Similarity Sequences and Similarity Sets In this section,we describe the L-similarity relation on *which is a generali- sation of the equivalence relation≡L(x≡Ly:xz∈L iff yz∈L for all z∈*). The notion of L-similarity was introduced in [7 and studied in [4 etc.In this paper,L-similarity is used to establish our algorithms. Let be an alphabet,L a finite language,and l the length of the longest word(s)in L.Let r,y*.We define the following relations: (1)x~L y if for all z∈D*such that xz≤I and yz≤l,xz∈L iff yz∈L: (2)xLy if ~Ly does not hold. The relation ~L is called similarity relation with respect to L. Note that the relation ~L is reflexive,symmetric,but not transitive.For example,let fa,b}and L faab,baa,aabb.It is clear that aab ~L aabb and baa ~L aabb,but aab L baa. The following lemma is obvious: Lemma 1 Let L∈∑*be a finite language and x,,z∈∑*，lzl≤lyl≤lz. The following statements hold: 1.If ~Ly,I ~L z,then y~L z. 2.If ~L y,y ~L z,then ~L z. 3.If ~Ly,y%Lz,then ILz. If zLy and yLz,we cannot say anything about the similarity relation between x and z. Erample1.Let,y,z∈∑*，zl≤lg≤lzl.We may have 1)xALy,y~L z and ~L z,or 2)Ly,y~L z and TyLz

Minimal Cover-Automata for Finite Languages 45 The language recognised by the automaton A is L(A) = {w ∈ Σ∗ | δ(q0, w) ∈ F}. For simplicity, we assume that Q = {0, 1,..., #Q − 1} and q0 = 0. In what follows we assume that δ is a total function, i.e., the automaton is complete. Let l be the length of the longest word(s) in the finite language L. A DFA A such that L(A) ∩ Σ≤l = L is called a deterministic finite cover-automaton (DFCA) of L. Let A = (Q, Σ, δ, 0, F) be a DFCA of a finite language L. We say that A is a minimal DFCA of L if for every DFCA B = (Q0 ,Σ,δ0 , 0, F0 ) of L we have #Q ≤ #Q0 . Let A = (Q, Σ, δ, 0, F) be a DFA. Then a) q ∈ Q is said to be accessible if there exists w ∈ Σ∗ such that δ(0, w) = q, b) q is said to be useful (coaccessible) if there exists w ∈ Σ∗ such that δ(q, w) ∈ F. It is clear that for every DFA A there exists an automaton A0 such that L(A0 ) = L(A) and all the states of A0 are accessible and at most one of the states is not useful (the sink state). The DFA A0 is called a reduced DFA. In what follows we shall use only reduced DFA. 3 Similarity Sequences and Similarity Sets In this section, we describe the L-similarity relation on Σ∗, which is a generalisation of the equivalence relation ≡L (x ≡L y: xz ∈ L iff yz ∈ L for all z ∈ Σ∗). The notion of L-similarity was introduced in [7] and studied in [4] etc. In this paper, L-similarity is used to establish our algorithms. Let Σ be an alphabet, L ⊆ Σ∗ a finite language, and l the length of the longest word(s) in L. Let x, y ∈ Σ∗. We define the following relations: (1) x ∼L y if for all z ∈ Σ∗ such that |xz| ≤ l and |yz| ≤ l, xz ∈ L iff yz ∈ L; (2) x 6∼L y if x ∼L y does not hold. The relation ∼L is called similarity relation with respect to L. Note that the relation ∼L is reflexive, symmetric, but not transitive. For example, let Σ = {a, b} and L = {aab, baa, aabb}. It is clear that aab ∼L aabb and baa ∼L aabb, but aab 6∼L baa. The following lemma is obvious: Lemma 1 Let L ⊆ Σ∗ be a finite language and x, y, z ∈ Σ∗, |x|≤|y|≤|z|. The following statements hold: 1. If x ∼L y, x ∼L z, then y ∼L z. 2. If x ∼L y, y ∼L z, then x ∼L z. 3. If x ∼L y, y6∼Lz, then x6∼Lz. If x 6∼L y and y ∼L z, we cannot say anything about the similarity relation between x and z. Example 1. Let x, y, z ∈ Σ∗, |x|≤|y|≤|z|. We may have 1) x6∼Ly, y ∼L z and x ∼L z, or 2) x6∼Ly, y ∼L z and x6∼Lz

46 Cezar Campeanu,Nicolae Santean,and Sheng Yu Indeed,if L [aa,aaa,bbb,bbbb,aaab we have 1)if we choose r aa,y bbb, z=bbbb,and 2)if we choose x aa,y bba,z abba. Definition 1.LetL∈∑*be a finite language. 1.A set S*is called an L-similarity set if ~Ly for every pair x,yE S. 2.A sequence of words ,...,n]over is called a dissimilar sequence ofL if i L Tj for each pair i,j,1≤i,j≤n and i≠j: 3.A dissimilar sequence 1,...]is called a canonical dissimilar sequence of L if there exists a partition=(51,...,Sn}of such that for each i, 1≤i≤n,xi∈Si,and Si is a L-similarity set. 4.A dissimilar sequence [1,...,In of L is called a marimal dissimilar se- quence of L if for any dissimilar sequence [y,...,yml of L,m n.Then there are yi and yj,ij, such that yi,j∈Sk for some k,1≤k≤n.Since Sk is a L-similarity set, yi~L yj.This is a contradiction.Then,the assumption that m >n is false,and we conclude that [r1,...,]is a maximal dissimilar sequence. Conversely,let [1,...,n]a maximal dissimilar sequence of L.Without loss of generality we can suppose that x1l≤..≤lzn.Fori=l,.·,n,define Xi=yE*y~L Ti and yg xi for j<i Note that for each y∈*，y~L i for at least one i,l≤i≤n,since[ri,.,xn] is a marimal dissimilar sequence.Thus,={X1,...,Xn}is a partition of The remaining task of the proof is to show that each Xi,1 i<n,is a similarity set. We assume the contrary,i.e.,for some i,1 i<n,there exist y,2E Xi such that yz.We know that zi~L y and zi~L z by the definition of Xi.We have the following three cases:(1)lz<lyl,lzl,(2)l≤lzil≤lz(or|zl≤zl≤l): and (3)il lyl,lzl.If (1)or (2),then y~Lz by Lemma 1.This would contra- dict our assumption.If(3),then it is easy to prove that yj and zj,for all ji,using Lemma 1 and the definition of Xi.Then we can replace ri by both y and z to obtain a longer dissimilar sequence [1,...,i-1,y,2,i+1,...,n]. This contradicts the fact that [1,...,-1,i,+1,...,n]is a maximal dis- similar sequence of L.Hence,y~z and Xi is a similarity set. Corollary 1.For each finite language L,there is a unique number N(L)which is the number of elements in any canonical dissimilar sequence of L

46 Cezar Cˆampeanu, Nicolae Sˆantean, and Sheng Yu Indeed, if L = {aa, aaa, bbb, bbbb, aaab} we have 1) if we choose x = aa, y = bbb, z = bbbb, and 2) if we choose x = aa, y = bba, z = abba. Definition 1. Let L ∈ Σ∗ be a finite language. 1. A set S ⊆ Σ∗ is called an L-similarity set if x ∼L y for every pair x, y ∈ S. 2. A sequence of words [x1,... ,xn] over Σ is called a dissimilar sequence of L if xi 6∼L xj for each pair i, j, 1 ≤ i, j ≤ n and i 6= j. 3. A dissimilar sequence [x1,... ,xn] is called a canonical dissimilar sequence of L if there exists a partition π = {S1,... ,Sn} of Σ∗ such that for each i, 1 ≤ i ≤ n, xi ∈ Si, and Si is a L-similarity set. 4. A dissimilar sequence [x1,... ,xn] of L is called a maximal dissimilar sequence of L if for any dissimilar sequence [y1,... ,ym] of L, m ≤ n. Theorem 1. A dissimilar sequence of L is a canonical dissimilar sequence of L if and only if it is a maximal dissimilar sequence of L. Proof. Let L be a finite language. Let [x1,... ,xn] be a canonical dissimilar sequence of L and π = {S1,... ,Sn} the corresponding partition of Σ∗ such that for each i, 1 ≤ i ≤ n, Si is an L-similarity set. Let [y1,... ,ym] be an arbitrary dissimilar sequence of L. Assume that m>n. Then there are yi and yj , i 6= j, such that yi, yj ∈ Sk for some k, 1 ≤ k ≤ n. Since Sk is a L-similarity set, yi ∼L yj. This is a contradiction. Then, the assumption that m>n is false, and we conclude that [x1,... ,xn] is a maximal dissimilar sequence. Conversely, let [x1,... ,xn] a maximal dissimilar sequence of L. Without loss of generality we can suppose that |x1| ≤ ... ≤ |xn|. For i = 1,... ,n, define Xi = {y ∈ Σ∗ | y ∼L xi and y 6∈ Xj for j |y|, |z|. If (1) or (2), then y ∼L z by Lemma 1. This would contradict our assumption. If (3), then it is easy to prove that y 6∼ xj and z 6∼ xj , for all j 6= i, using Lemma 1 and the definition of Xi. Then we can replace xi by both y and z to obtain a longer dissimilar sequence [x1,... ,xi−1, y, z, xi+1,... ,xn]. This contradicts the fact that [x1,...,xi−1, xi, xi+1,... ,xn] is a maximal dissimilar sequence of L. Hence, y ∼ z and Xi is a similarity set. Corollary 1. For each finite language L, there is a unique number N(L) which is the number of elements in any canonical dissimilar sequence of L

Minimal Cover-Automata for Finite Languages 47 Theorem 2.Let S1 and S2 be two L-similarity sets and r1 and x2 the shortest words in S1 and S2,respectively.If ~Lx2 then SUS2 is a L-similarity set. Proof.It suffices to prove that for an arbitrary word y E S and an arbitrary word y2 E S2,y ~L y2 holds.Without loss of generality,we assume that lzl≤lz2l.We know that il≤lyl and2l≤ly2l.Since z1~Lx2and T2 ~L y2,we have I ~L y2 (Lemma 1 (2)),and since r1 ~L y and I ~L y2, we have y1 ~L y2 (Lemma 1 (1)). 4 Similarity Relations on States Let A=(Q,,6,0,F)be a DFA and L=L(A).Then it is clear that if 6(0,x)= 6(0,y)=g for some gEQ,then x =Ly and,thus,~Ly.Therefore,we can also define equivalence as well as similarity relations on states. Definition 2.Let A=(Q,S,6,0,F)be a DFA.We define,for each state gEQ, level(q)=minw6(0,w)=gh, i.e.,level(q)is the length of the shortest path from the initial state to q. Definition 3.Let A (Q,S,6,0,F)be a DFA and LL(A).We say that p≡Aq(state p is equivalent to q in A)if for every w∈∑*，6(s,w)∈Ff 6(q,w)∈F. Definition 4.Let A (Q,S,6,0,F)be a DFCA of a finite language L.Let level(p)=i and level(q)=j,m maxfi,j.We say that p~A q (state p is L-similar to q in A)if for every w∈≤1-m,6(p,w)∈Ff6(g,w)∈F. IfA=(Q,∑，6,0，F)is a DFA,for each q∈Q,we denote A(g)=min{w| 6(0,w)=a},where the minimum is taken according to the quasi-lexicographical order,and LA(g)={w∈∑*|6(q,w)∈F}.When the automaton A is under stood,we write o instead of A(q)and Lg instead LA(g). Lemma2LetA=(Q,∑，d,0,F)be a DFCA of a finite language L.Letx,y∈ such that 6(0,x)=p and 6(0,y)=q.If p~Aq then ~Ly. Proof.Let level(p)=i and level(q)=j,m =maxti,j,and p~Aq.Choose an arbitrary w∈D*such that xw≤l and |yw≤l.Because i≤x and j≤llit follows thatw≤l-m.Since p~A g we have that6(p,w)∈Fif6(g,w)∈F i.e.6(0,xw)∈Fif6(0,yw)∈F,which means that rw∈L(A)fyw∈L(A). Hence ~Ly. Lemma 3 Let A=(Q,S,6,0,F)be DFCA of a finite language L.Let level(p)= iand level(g)=j,m=max{i,j},andx∈，y∈such that6(0,E)=p and 6(0,y)=q.If ~L y then p~A q

Minimal Cover-Automata for Finite Languages 47 Theorem 2. Let S1 and S2 be two L-similarity sets and x1 and x2 the shortest words in S1 and S2, respectively. If x1 ∼L x2 then S1 ∪ S2 is a L-similarity set. Proof. It suffices to prove that for an arbitrary word y1 ∈ S1 and an arbitrary word y2 ∈ S2, y1 ∼L y2 holds. Without loss of generality, we assume that |x1|≤|x2|. We know that |x1|≤|y1| and |x2|≤|y2|. Since x1 ∼L x2 and x2 ∼L y2, we have x1 ∼L y2 (Lemma 1 (2)), and since x1 ∼L y1 and x1 ∼L y2, we have y1 ∼L y2 (Lemma 1 (1)). 4 Similarity Relations on States Let A = (Q, Σ, δ, 0, F) be a DFA and L = L(A). Then it is clear that if δ(0, x) = δ(0, y) = q for some q ∈ Q, then x ≡L y and, thus, x ∼L y. Therefore, we can also define equivalence as well as similarity relations on states. Definition 2. Let A = (Q, Σ, δ, 0, F) be a DFA. We define, for each state q ∈ Q, level(q) = min{|w| | δ(0, w) = q}, i.e., level(q) is the length of the shortest path from the initial state to q. Definition 3. Let A = (Q, Σ, δ, 0, F) be a DFA and L = L(A). We say that p ≡A q (state p is equivalent to q in A) if for every w ∈ Σ∗, δ(s, w) ∈ F iff δ(q, w) ∈ F. Definition 4. Let A = (Q, Σ, δ, 0, F) be a DFCA of a finite language L. Let level(p) = i and level(q) = j, m = max{i, j}. We say that p ∼A q (state p is L-similar to q in A) if for every w ∈ Σ≤l−m, δ(p, w) ∈ F iff δ(q, w) ∈ F. If A = (Q, Σ, δ, 0, F) is a DFA, for each q ∈ Q, we denote xA(q) = min{w | δ(0, w) = q}, where the minimum is taken according to the quasi-lexicographical order, and LA(q) = {w ∈ Σ∗ | δ(q, w) ∈ F}. When the automaton A is understood, we write xq instead of xA(q) and Lq instead LA(q). Lemma 2 Let A = (Q, Σ, δ, 0, F) be a DFCA of a finite language L. Let x, y ∈ Σ∗ such that δ(0, x) = p and δ(0, y) = q. If p ∼A q then x ∼L y. Proof. Let level(p) = i and level(q) = j, m = max{i, j}, and p ∼A q. Choose an arbitrary w ∈ Σ∗ such that |xw| ≤ l and |yw| ≤ l. Because i ≤ |x| and j ≤ |y| it follows that |w| ≤ l − m. Since p ∼A q we have that δ(p, w) ∈ F iff δ(q, w) ∈ F, i.e. δ(0, xw) ∈ F iff δ(0, yw) ∈ F, which means that xw ∈ L(A) iff yw ∈ L(A). Hence x ∼L y. Lemma 3 Let A = (Q, Σ, δ, 0, F) be DFCA of a finite language L. Let level(p) = i and level(q) = j, m = max{i, j}, and x ∈ Σi , y ∈ Σj such that δ(0, x) = p and δ(0, y) = q. If x ∼L y then p ∼A q

Minimal Cover-Automata for Finite Languages 49 The proof is left to the reader.The next lemma is obvious. Lemma 6 Let A =(Q,5,6,0,F)be a DFCA of a finite language L.Let i= level(p)andj=level(q),i≤j.Letp~Lq.Letw=w1.wn∈∑sand p:=60,w1.w),1≤i≤n.Then w∈L iff Tkwk.+1.wn∈Lfor1≤k≤n. Lemma 7 Let A=(Q,6,0,F)be a DFCA of a finite language L.If p~Aq for some p,q∈Q,i=level(p),j=level(q)andi≤j,p≠q,q≠0.then we can construct a DFCA A'=(Q',∑，6'，0，F)of L such that Q'=Q-{q}, F=F-{q),and '(s,a)= ∫(s,a）f(s,a)≠g, p 6(s,a)=9 for each s EQ'and a E.Thus,A is not a minimal DFCA of L. Proof.It suffices to prove that A'is a DFCA of L.Let I be the length of the longest word(s)in L and assume that level(p)=i and level(q)=j,i<j. Consider a word w∈∑sL.We now prove that w∈Lif6'(0,w)∈F'. If there is no prefix wi of w such that 6(0,w1)=q,then clearly 6(0,w)EF iff 6(0,w)E F.Otherwise,let w w1w2 where w is the shortest prefix of w such that 6(0,w1)=g.In the remaining,it suffices to prove that 6'(p,w2)EF iff 6(q,w2)E F.We prove this by induction on the length of w2.First consider the case2l=0,i.e,w2=X.Since p~Aq,p∈Fifq∈F.Then p∈F'ifq∈F by the construction of A'.Thus,6'(p,w2)EF iff 6(q,w2)E F.Suppose that the statement holds for w2l<I'for /<I-wl.(Note that I-wl<l-j.) Consider the case that w2l=1'.If there does not exist u such that u≤pw2and6p,w）=g,then6p,w2)∈F-{q}if6(g,2)∈F-{q},i.e, 6'(p,w2)E F iff 6(q,w2)E F.Otherwise,let w2 uv and u be the shortest nonempty prefix of w2 such that 6(p,u)=q.Then <I'(and 6'(p,u)=p). By induction hypothesis,6'(p,v)EF iff 6(q,v)E F.Therefore,6'(p,uv)EF if6(q,uw)∈F. Lemma 8 Let A be a DFCA of L and L'=L(A).Then =Ly implies ~Ly. Proof.It is clear that if x =Ly then x~Ly.Let l be the length of the longest word(s)inL.Ltx≡L'y.So,for each z∈∑*，xz∈L'ifyz∈L'.We now consider all words z∈D*,such that|xz|≤land|yz<I.SinceL=L'n∑s and xz∈L'ifyz∈L',we have zz∈L iff yz∈L.Therefore,x~Ly by the definition of ~L. Corollary 4.Let A=(Q,5,6,0,F)be a DFCA of a finite language L,L'= L(A).Then p =Aq implies p~Lq. Corollary 5.A minimal DFCA of L is a minimal DFA

Minimal Cover-Automata for Finite Languages 49 The proof is left to the reader.The next lemma is obvious. Lemma 6 Let A = (Q, Σ, δ, 0, F) be a DFCA of a finite language L. Let i = level(p) and j = level(q), i ≤ j. Let p ∼L q.Let w = w1 ...wn ∈ Σ≤l and pi = δ(0, w1 ...wi), 1 ≤ i ≤ n. Then w ∈ L iff xkwk+1 ...wn ∈ L for 1 ≤ k ≤ n. Lemma 7 Let A = (Q, Σ, δ, 0, F) be a DFCA of a finite language L. If p ∼A q for some p, q ∈ Q, i = level(p), j = level(q) and i ≤ j, p 6= q, q 6= 0. then we can construct a DFCA A0 = (Q0 ,Σ,δ0 , 0, F0 ) of L such that Q0 = Q − {q}, F0 = F − {q}, and δ0 (s, a) = δ(s, a) if δ(s, a) 6= q, p δ(s, a) = q for each s ∈ Q0 and a ∈ Σ. Thus, A is not a minimal DFCA of L. Proof. It suffices to prove that A0 is a DFCA of L. Let l be the length of the longest word(s) in L and assume that level(p) = i and level(q) = j, i ≤ j. Consider a word w ∈ Σ≤L. We now prove that w ∈ L iff δ0 (0, w) ∈ F0 . If there is no prefix w1 of w such that δ(0, w1) = q, then clearly δ0 (0, w) ∈ F0 iff δ(0, w) ∈ F. Otherwise, let w = w1w2 where w1 is the shortest prefix of w such that δ(0, w1) = q. In the remaining, it suffices to prove that δ0 (p, w2) ∈ F0 iff δ(q, w2) ∈ F. We prove this by induction on the length of w2. First consider the case |w2| = 0, i.e., w2 = λ. Since p ∼A q, p ∈ F iff q ∈ F. Then p ∈ F0 iff q ∈ F by the construction of A0 . Thus, δ0 (p, w2) ∈ F0 iff δ(q, w2) ∈ F. Suppose that the statement holds for |w2| < l0 for l 0 ≤ l − |w1|. (Note that l − |w1| ≤ l − j.) Consider the case that |w2| = l 0 . If there does not exist u ∈ Σ+ such that u p w2 and δ(p, u) = q, then δ(p, w2) ∈ F − {q} iff δ(q, w2) ∈ F − {q}, i.e., δ0 (p, w2) ∈ F0 iff δ(q, w2) ∈ F. Otherwise, let w2 = uv and u be the shortest nonempty prefix of w2 such that δ(p, u) = q. Then |v| < l0 (and δ0 (p, u) = p). By induction hypothesis, δ0 (p, v) ∈ F0 iff δ(q, v) ∈ F. Therefore, δ0 (p, uv) ∈ F0 iff δ(q, uv) ∈ F. Lemma 8 Let A be a DFCA of L and L0 = L(A). Then x ≡L0 y implies x ∼L y. Proof. It is clear that if x ≡L y then x ∼L y. Let l be the length of the longest word(s) in L. Let x ≡L0 y. So, for each z ∈ Σ∗, xz ∈ L0 iff yz ∈ L0 . We now consider all words z ∈ Σ∗, such that | xz |≤ l and | yz |≤ l. Since L = L0 ∩ Σ≤l and xz ∈ L0 iff yz ∈ L0 , we have xz ∈ L iff yz ∈ L. Therefore, x ∼L y by the definition of ∼L. Corollary 4. Let A = (Q, Σ, δ, 0, F) be a DFCA of a finite language L, L0 = L(A). Then p ≡A q implies p ∼L q. Corollary 5. A minimal DFCA of L is a minimal DFA

Minimal Cover-Automata for Finite Languages 51 5.1 Determining Similarity Relation between States The aim is to present an algorithm which determines the similarity relations between states. LetA=(∑，Q,0,d,F)a DFCA of a finite language L.For each s∈Qlet Ys=minfw 6(s,w)E F,where minimum is taken according to the quasi- lexicographical order.Define Di={sEQy=i,for each i=0,1,.... Lemma9LetA=(∑，Q,0,d,F)a DFCA of a finite language L,ands∈Di, p∈Dj:Ifi≠j then sp. Proof.We can assume that i<j.Then obviously 6(s,)E F and 6(p,7)F. Since l2 Il+Ysl,I Ipl +lypl,and i<j,it follows that sl<lpl.So,we have that l min(I-Il,I-Ipl).Hence,sxp. Lemma 10 Let A=(Q,,0,6,F)be a reduced ordered DFA accepting L,p,qE Q-{#Q-1,where #Q-1 is the sink state,and either p,qe F or p,qg F. If for all aE,6(p,a)~A 6(q,a),then pAq. Proof.Let a and 6(p,a)=r and 6(g,a)=s.If r ~A s then for all wl, w<l-maxtA(s),xA(r)),A(r)w EL iff xA(s)w E L.Using Lemma 2 we also have:xA(q)aw∈LA(s)w∈L for all w∈*，lwl≤l-lzA(s)|and xA(p)aw∈LfxA(r)w∈L for all w∈∑*，lwl≤l-zA(r)儿 Hence zA(p)aw∈LiffA(q)aw∈L,for all w∈D*,lwl≤l-max{lzA(r)l, IA(s)I}.Because A(r)I A(q)al A(q)+1 and IA(s)<IA(p)al lzA(pl+1,we get zA(p)aw∈Lff A(q)aw∈L,for all w∈，lwl≤ I-max{A(p),A(q)}-1. Since a∈∑is chosen arbitrary,we conclude that A(p)w∈LffA(q)w∈L, for all w∈∑*，lw≤l-max{lzA(pl,lzA(ql},i.e.xA(p)~AxA(q).Therefore by using Lemma 3,we get that p~A q. Lemma 11 Let A=(Q,∑，0，d,F)be a reduced ordered DFA accepting L such that 6(0,w)=s implies w=s for all s EQ.Let p,qEQ-{#Q-1},where #Q-1 is the sink state.If there exists a E such that 6(p,a)A(q,a),then P7Aq- Proof..Suppose that p~Aq.then for all aw∈-m,6p,aw)∈Fif6(g,aw)∈ F,where m maxflevel(p),level(q)}.So 6(6(p,a),w)E F iff 6(6(q;a),w)E F for all w e Sl-m-1.Since s(p.a)l =lpl +1 and ls(d.a)=+1 it follows by definition that 6(p,a)~A 6(g,a).This is a contradiction. Our algorithm for determining the similarity relation between the states of a DFA (DFCA)of a finite language is based on Lemmas 10 and 11.However, most of DFA (DFCA)do not satisfy the condition of Lemma 11.So,we shall first transform the given DFA (DFCA)into one that does. LetA=(QA,∑，0,6A,FA）be a DFCA of L.We construct the minimal DFA for the language s,B=(QB,∑，0，dB,FfB)(QB={0,.·,l,l+1

Minimal Cover-Automata for Finite Languages 51 5.1 Determining Similarity Relation between States The aim is to present an algorithm which determines the similarity relations between states. Let A = (Σ, Q, 0, δ, F) a DFCA of a finite language L. For each s ∈ Q let γs = min{w | δ(s, w) ∈ F}, where minimum is taken according to the quasilexicographical order. Define Di = {s ∈ Q | |γs| = i}, for each i = 0, 1,... . Lemma 9 Let A = (Σ, Q, 0, δ, F) a DFCA of a finite language L, and s ∈ Di, p ∈ Dj . If i 6= j then s6∼p. Proof. We can assume that i<j. Then obviously δ(s, γs) ∈ F and δ(p, γs) ∈/ F. Since l ≥ |xs| + γs|, l ≥ |xp| + |γp|, and i<j, it follows that |γs| < |γp|. So, we have that |γs| ≤ min(l − |xs|, l − |xp|). Hence, s6∼p. Lemma 10 Let A = (Q, Σ, 0, δ, F) be a reduced ordered DFA accepting L, p, q ∈ Q − {#Q − 1}, where #Q − 1 is the sink state, and either p, q ∈ F or p, q 6∈ F. If for all a ∈ Σ, δ(p, a) ∼A δ(q, a), then p∼Aq. Proof. Let a ∈ Σ and δ(p, a) = r and δ(q, a) = s. If r ∼A s then for all |w|, |w| < l − max{xA(s), xA(r)}, xA(r)w ∈ L iff xA(s)w ∈ L. Using Lemma 2 we also have: xA(q)aw ∈ L iff xA(s)w ∈ L for all w ∈ Σ∗, |w| ≤ l − |xA(s)| and xA(p)aw ∈ L iff xA(r)w ∈ L for all w ∈ Σ∗, |w| ≤ l − |xA(r)|. Hence xA(p)aw ∈ L iff xA(q)aw ∈ L, for all w ∈ Σ∗, |w| ≤ l − max{|xA(r)|, |xA(s)|}. Because |xA(r)|≤|xA(q)a| = |xA(q)| + 1 and |xA(s)|≤|xA(p)a| = |xA(p)| + 1, we get xA(p)aw ∈ L iff xA(q)aw ∈ L, for all w ∈ Σ∗, |w| ≤ l − max{|xA(p)|, |xA(q)|} − 1. Since a ∈ Σ is chosen arbitrary, we conclude that xA(p)w ∈ L iff xA(q)w ∈ L, for all w ∈ Σ∗, |w| ≤ l − max{|xA(p)|, |xA(q)|}, i.e. xA(p) ∼A xA(q). Therefore, by using Lemma 3, we get that p ∼A q. Lemma 11 Let A = (Q, Σ, 0, δ, F) be a reduced ordered DFA accepting L such that δ(0, w) = s implies |w| = |xs| for all s ∈ Q. Let p, q ∈ Q − {#Q − 1}, where #Q − 1 is the sink state. If there exists a ∈ Σ such that δ(p, a)6∼Aδ(q, a), then p6∼Aq. Proof. Suppose that p ∼A q. then for all aw ∈ Σl−m, δ(p, aw) ∈ F iff δ(q, aw) ∈ F, where m = max{level(p), level(q)}. So δ(δ(p, a), w) ∈ F iff δ(δ(q, a), w) ∈ F for all w ∈ Σl−m−1. Since |xδ(p,a)| = |xp| + 1 and |xδ(q,a)| = |xq| + 1 it follows by definition that δ(p, a) ∼A δ(q, a). This is a contradiction. Our algorithm for determining the similarity relation between the states of a DFA (DFCA) of a finite language is based on Lemmas 10 and 11. However, most of DFA (DFCA) do not satisfy the condition of Lemma 11. So, we shall first transform the given DFA (DFCA) into one that does. Let A = (QA,Σ, 0, δA, FA) be a DFCA of L. We construct the minimal DFA for the language Σ≤l , B = (QB,Σ, 0, δB, FB) (QB = {0, . . . ,l,l + 1}

52 Cezar Cˆampeanu, Nicolae Sˆantean, and Sheng Yu δB(i, a) = i + 1, for all i, 0 ≤ i ≤ l, δB(l + 1, a) = l + 1, for all a ∈ Σ, FB = {0,... ,l}). The DFA B will have exact l + 2 states. Now we use the standard Cartesian product construction (see, e.g., [3], for details) for the DFA C = (QC ,Σ,q0, δC , FC ) such that L(C) = L(A) ∩ L(B), and we eliminate all inaccessible states. Obviously, L(C) = L and C satisfies the condition of Lemma 11. The next lemma is easy to prove and left for the reader. Lemma 12 For the DFA C constructed above we have (p, q) ∼C (p, r). Lemma 13 For the DFA C constructed above, if δC ((0, 0), w)=(p, q), then |w| = q. Proof. We have δC((0, 0), w)=(p, q), so δB(0, w) = q so |w| = q. Now we are able to present an algorithm, which determines the similarity relation between the states of C. Note that QC is ordered by that (pA, pB) < (qA, qB) if pA < qA or pA = qA and pB < qB. Attaching to each state of C is a list of similar states. For α, β ∈ QC, if α ∼C β and α<β, then β is stored on the list of similar states for α. We assume that QA = {0, 1,... ,n} and n is the sink state of A. 1. Generate the DFA B for the language Σ≤l . 2. Compute the DFA C such that L(C) = L(A) ∩ L(B) using the standard Cartesian product algorithm (see [3] for details). 3. Compute Di of C, 0 ≤ i ≤ l. 4. Initialize the similarity relation by specifying: – For all (n, p),(n, q) ∈ QC , (n, p) ∼C (n, q). – For all (n, l + 1 − i) ∈ QC , (n, l + 1 − i) ∼C α for all α ∈ Dj , j = i, . . . , l, 0 ≤ i ≤ l. 5. For each Di, 0 ≤ i ≤ l, create a list Listi, which is initialized to ∅. 6. For each α ∈ QC − {(n, q) | q ∈ QB}, following the reversed order of QC, do the following: Assuming α ∈ Di. – For each β ∈ Listi, if δC (α, a) ∼C δC (β, a) for all a ∈ Σ, then α ∼C β. – Put α on the list Listi. Remark 2. The above algorithm has complexity O((n × l)2), where n is the number of states of the initial DFA (DFCA) and l is the maximum accepted length for the finite language L. 5.2 The Construction of a Minimal DFCA As input we have the above DFA C and, with each α ∈ QC , a set Sα = {β ∈ QC | α ∼C β and α<β}. The output is D = (QD,Σ,δD, q0, FD), a minimal DFCA for L