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 quasi￾lexicographical 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}