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 generali￾sation 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