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 T<=Ti.We say =0 that x is a prefix of y,denoted rpy,if y=xz for some zT+.The relation p is a partial order on T*.If T ={t1,...,t}is an ordered set,k >0,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 <l = l [−1 i=0 T i . We say that x is a prefix of y, denoted x p y, if y = xz for some z ∈ T ∗.The relation p is a partial order on T ∗. If T = {t1,... ,tk} is an ordered set, k > 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. Theorem 1.A dissimilar sequence of L is a canonical dissimilar sequence of L if and only if it is a marimal dissimilar sequence of L. Proof.Let L be a finite language.Let [r1,...,n]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 [y,...,ym]be an arbitrary dissimilar sequence of L.Assume that 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<i}. Note that for each y ∈ Σ∗, y ∼L xi for at least one i, 1 ≤ i ≤ n, since [x1,...,xn] is a maximal 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, z ∈ Xi such that y6∼Lz. We know that xi ∼L y and xi ∼L z by the definition of Xi. We have the following three cases: (1) |xi| < |y|, |z|, (2) |y|≤|xi|≤|z| (or |z|≤|xi|≤|y|), and (3) |xi| > |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