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