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 se￾quence 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 contra￾dict 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 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