# A Remark on Myhill-Nerode Theorem for Fuzzy Languages

Authors: Shou-feng Wang
Journal: Journal of Applied Mathematics
 (2012)

---

## Abstract

Regular fuzzy languages are characterized by some algebraic approaches. In particular, an
extended version of Myhill-Nerode theorem for fuzzy languages is obtained.


---

## Body

## 1. Introduction

Fuzzy sets were introduced by Zadeh in [1] and since
then have appeared in many fields of sciences. They have been studied within automata theory
for the first time by Wee in [2]. More on recent
development of algebraic theory of fuzzy automata and formal fuzzy languages can be found in
the book Mordeson and Malik [3], the texts Malik et
al. [4, 5], and
Petković [6].A fuzzy language is calledregular if it can be recognized by a fuzzy
automaton. In the texts Mordeson and Malik [3],
Petković [6], Ignjatovic et al. [7], and Shen [8],
regular fuzzy languages have been characterized by the principal
congruences (principal right congruences, principal left
congruences) determined by fuzzy languages, which are known as
Myhill-Nerode theorem for fuzzy languages. Moreover, Petković
[6] also considered the varieties of fuzzy languages
and Ignjatovic and Ciric [9] considered regular
operations of fuzzy languages.Recently, Wang et al. [10] generalized the usual
principal congruences (resp., principal right congruences, principal left congruences) to
some kinds of generalized principal congruences (resp., generalized
principal right congruences, generalized principal left congruences) determined
by crisp languages by using prefix-suffix-free subsets (resp.,
prefix-free languages, suffix-free languages) and obtained some
characterizations of regular crisp languages.In this note, we will realize the idea of the text [10] for fuzzy languages. In other word, we characterize regular fuzzy languages by
some kinds of generalized principal congruences (resp., generalized principal right
congruences, generalized principal left congruences) determined by fuzzy languages. In
particular, we obtain an extended version of Myhill-Nerode theorem for fuzzy languages.


## 2. Preliminaries

Throughout the paper,A is a finite set which is called an alphabet
and A* is the free monoid generated by A, that is, the set of all words with letters from
A. The empty word is denoted by 1. The length of a word w in A* is the number of letters appearing in
w and is denoted by |w|. The complement of a subset
L of A* is the set L¯={w∈A*∣w∉L}. A subset L of A* is cofinite if L¯ is finite. A nonempty subset S of A* is called a suffix-free language overA if no element in S is a suffix of another element in S. Prefix-free languages overA can be defined dually. On the other hand, a nonempty subset
L of A* is called a prefix-closed language overA if any prefix of an element in L is also in L.As an analogue of prefix-free languages and suffix-free languages overA, Wang et al. [10]
introduced prefix-suffix-free subsets of A*×A*. A subset Δ of the set A*×A* is called a prefix-suffix-free subset if for
all words s,t,x,y in A*, the following holds: if both (s,t) and (sx,yt) are in Δ, then x=y=1.An equivalenceρ on A* is called a right congruence if
xρy implies that xzρyz for any x,y,z∈A*. A left congruences can be defined dually. An equivalence is
a congruence if it is a right congruence and also a left congruence.Afuzzy subsetα of a set X is a mapping α:X→[0,1]. By ∧ and ∨ infimum and supremum in the unit segment
[0,1] will be denoted, respectively. Every element
y of X can be considered as the following fuzzy subset of
X: (2.1)y(x)=1forx=y,y(x)=0forx≠y. A fuzzy language over
A is a fuzzy subset of A*. A fuzzy language is regular if it is
recognizable by a fuzzy automaton from the book [3].
For a fuzzy language λ over A, the relations defined on A* by the following: (2.2)xPλ(r)yifλ(xu)=λ(yu)foreveryuinA*,xPλ(l)yifλ(ux)=λ(uy)foreveryuinA*,xPλyifλ(uxv)=λ(uyv)foreveryu,v∈A*, are called the principal right congruence
(resp., principal left congruence, principal congruence) determined by
λ, respectively.Now, we state the well-known Myhill-Nerode theorem for fuzzy languages which gives some
algebraic characterizations for regular fuzzy languages. Recall thatthe
index of an equivalence ρ on A* is the number of ρ-classes of A*.Theorem 2.1 (see [3, 6, 8], Myhill-Nerode theorem).
For a fuzzy languageλ over A, the following statements are equivalent:(1)
λis regular.(2)
Pλ is of finite index.(3)
Pλ(r) is of finite index.(4)
Pλ(l) is of finite index.In the sequel, we recall some operations of fuzzy languages. For two fuzzy languagesλ1 and λ2 over A, the union, intersection, product, and left and right
quotients of λ1 and λ2 are defined, respectively, by the following:
(2.3)(λ1∪λ2)(w)=λ1(w)∨λ2(w),(λ1∩λ2)(w)=λ1(w)∧λ2(w),(λ1λ2)(w)=⋁xy=w(λ1(x)∧λ2(y))(λ1-1λ2)(w)=⋁u∈A*(λ2(uw)∧λ1(u)),(λ2λ1-1)(w)=⋁u∈A*(λ2(wu)∧λ1(u)). Further, we also define left-right quotient of
three fuzzy languages λ1, λ2 and λ over A by the following: (2.4)(λ1-1λλ2-1)(w)=[(λ1-1λ)λ2-1](w). Observe that (s-1λt-1)(w)=λ(swt) for any s,t,w∈A* with the above notations.On regular fuzzy languages, we have the following.Lemma 2.2 (see [6]).
Finite unions, intersections, products, and left-right quotients of regular fuzzy
languages overA are regular.


## 3. Main Result

In this section, we shall introduce some kinds of generalized principal (resp., right,
left) congruences determined by fuzzy languages by using prefix-suffix-free subsets (resp.,
prefix-free languages, suffix-free languages) and give an extended version of Myhill-Nerode
theorem for fuzzy languages.Now, letP be a prefix-free language, S be a suffix-free language over A, Δ be a prefix-suffix-free subset of A*×A*, and λ be a fuzzy language over A, respectively. For a prefix-suffix-free subset
Δ, denote (3.1)ΩΔ={(sx,yt)∣(s,t)∈Δ,x,y∈A*},N(Δ)=⋃(s,t)∈ΔsA*t. Define the following relations on A*: (3.2)xPP,λ(l)yifλ(ux)=λ(uy)foreveryuinPA*,xPS,λ(r)yifλ(xu)=λ(yu)foreveryuinA*S,xPΔ,λyifλ(uxv)=λ(uyv)forevery(u,v)inΩΔ,xPF,S,λ(r)yifthereexistssomefinitesubsetFofA*suchthatλ(xu)=λ(yu)foreveryuinFA*S¯¯,xPF,P,λ(l)yifthereexistssomefinitesubsetFofA*suchthatλ(ux)=λ(uy)foreveryuinPA*¯F¯. Then we have the following observations.Proposition 3.1.
The abovePS,λ(r),Pℱ,S,λ(r)(resp.,PP,λ(l),Pℱ,P,λ(l);PΔ,λ) are right congruences (resp., left congruences; congruence)
on A*. Furthermore, (3.3)Pλ(r)⊆PS,λ(r)⊆PF,S,λ(r),Pλ(l)⊆PP,λ(l)⊆PF,P,λ(l),Pλ⊆PΔ,λ.Proof.
It is easy to check thatPS,λ(r) (resp., PP,λ(l)) is a right (resp., left) congruence,
PΔ,λ is a congruence, and (3.4)Pλ(r)⊆PS,λ(r)⊆PF,S,λ(r),Pλ(l)⊆PP,λ(l)⊆PF,P,λ(l),Pλ⊆PΔ,λ by their definitions. In the sequel, we show that
Pℱ,S,λ(r) is a right congruence and Pℱ,P,λ(l) is a left congruence. Clearly, both
Pℱ,S,λ(r) and Pℱ,P,λ(l) are equivalences. Now, let x,y be two words in A* and xPℱ,S,λ(r)y. Then there exists a finite subset
F of A* such that λ(xu)=λ(yu) for any u in FA*S¯¯. Now, let z be a word in A* and F′ be the union of {w∈A*∣zw∈F} and {1}. Then zu is in FA*S¯¯ for any u in F′A*S¯¯. This implies that λ(xzu)=λ(yzu) for any u in F′A*S¯¯ whence xzPℱ,S,λ(r)yz since F′ is finite. Thus, Pℱ,S,λ(r) is a right congruence. Dually, Pℱ,P,λ(l) is a left congruence.Remark 3.2.
Note that the above inclusions are all proper in general. For example, letA={a},S={a2} and F={1,a,a2,a3}. Then FA*S¯¯=A*a5. Define a fuzzy language over A as follows: (3.5)λ(w)=αforw∈{a2,a3},λ(w)=βforw∈A*∖{a2,a3}, where α,β are in [0,1] and α≠β. Then we have (3.6)(a3,a4)∉Pλ(r),(a3,a4)∈PS,λ(r),(1,a2)∉PS,λ(r),(1,a2)∈PF,S,λ(r). Similarly, we can show that the remainder inclusions are all
proper.To obtain our main result, we need a series of lemmas. First, we recall the followingalphabetic order “≤” on A*: For two words u and v in A* with different lengths, u<v if |u|<|v|, for two words with same length, the order is the
lexicographic order. Observe that the alphabetic order is a well order on
A*. We have the following result.Lemma 3.3.
LetL be an infinite prefix-closed language over
A. Then there exists an infinite subset
{1,a1,a1a2,…,a1a2,…,an,…} of L, where ai∈A.Proof.
Denote(3.7)PrefA(L)={a∈A∣(∃y∈A*)ay∈L}. Observe that A is finite and L is infinite, there exists L1⊆L and a1∈A such that L1 is infinite and PrefA(L1)={a1}. Denote (3.8)a1-1L1={w∈A*∣a1w∈L1}. Then a1-1L1 is infinite. Hence, there also exists
L2⊆a1-1L1 and a2∈A such that L2 is infinite and PrefA(L2)={a2}. In general, for any positive integer
n, there exists Ln+1⊆an-1Ln and an+1∈A such that Ln+1 is infinite and PrefA(Ln+1)={an+1}. Let (3.9)C={1,a1,a1a2,a1a2a3,…,a1a2a3⋯an,…}. Clearly, C is infinite. We claim that C⊆L. Let a1a2a3⋯an∈C. Observe that (3.10)Ln⊆an-1-1Ln-1⊆an-1-1an-2-1Ln-2⊆⋯⊆an-1-1an-2-1⋯a1-1L1=(a1a2⋯an-1)-1L1,{an}=PrefA(Ln)⊆PrefA((a1a2⋯an-1)-1L1). Therefore, there exists y∈A* such that any∈(a1a2⋯an-1)-1L1. And hence, a1a2⋯an-1any∈L1⊆L. Since L is prefix-closed, a1a2⋯an-1an∈L. This implies that C⊆L.Lemma 3.4.
Letρ be a right congruence on A* and {Li∣i∈I} be the set of all ρ-classes of A*. Then, (3.11)Lρ={si∣siistheleastelementinLiwithrespectto“≤",i∈I} is prefix-closed.Proof.
Clearly,1 is in Lρ. Let sj be in Lρ and sj=a1a2⋯at for some positive integer t>1 and a1,a2,…,at in A. Then, a1a2⋯at-1 is not in Lj. Suppose that a1a2⋯at-1 is in Lk. Then, sk≤a1a2⋯at-1. This implies that skat≤a1a2⋯at-1at=sj. On the other hand, since skρa1a2⋯at-1 and ρ is a right congruence, we have skatρsj. Hence, skat is in Lj and so skat≥sj. Thus, skat=sj=a1a2a3⋯at-1at. This implies that sk=a1a2a3⋯at-1 whence a1a2a3⋯at-1 is in Lρ.Lemma 3.5.
LetS be a suffix-free language and λ be a fuzzy language over A.(1)
P{1}×S,λ is of finite index if and only if
PS,λ(r) is of finite index.(2)
PS,λ(r) is of finite index if and only if
Pℱ,S,λ(r) is of finite index.Proof.
(1)  Similar to the proof of Proposition  3.11 in [10].
(2) Observe thatPS,λ(r)⊆Pℱ,S,λ(r), the necessity holds. Conversely, if
Pℱ,S,λ(r) is of finite index and PS,λ(r) is of infinite index, then by Lemma 3.4, LPS,λ(r) is infinite and prefix-closed. By Lemma 3.3, there exists an infinite subset
(3.12)C={1,a1,a1a2,⋯,a1a2⋯an,…}, of LPS,λ(r), where ai∈A. Since Pℱ,S,λ(r) is of finite index, there exist two distinct elements
x,y∈C such that xPℱ,S,λ(r)y. Therefore, there exists a finite subset
F of A* such that λ(xu)=λ(yu)foreveryuinFA*S¯¯. Denote T=max{|f|∣f∈F} and take u in A* satisfying |u|>T. We assert that uv is in FA*S¯¯ for any v in A*S. In fact, if uv=fw for some f in F and w in A*S¯, then by the choice of u, f is a prefix of u and so v is a suffix of w whence w is in A*S. A contradiction. Therefore, for any
v in A*S, we have λ(xuv)=λ(yuv). This implies that xuPS,λ(r)yu.
Without loss of generality, we letx<y with respect to the alphabetic order,
y=a1a2⋯at and u=at+1⋯at+T+1. Then, by the above discussions, xuPS,λ(r)yu and yu is in C. Observe that C is a subset of LPS,λ(r), in view of the definition of LPS,λ(r), xu≥yu. This implies that x≥y. A contradiction.Lemma 3.6.
LetS be a finite suffix-free language over
A. Then A*S is cofinite if and only if S is maximal.Proof.
It follows from Lemma  3.14 in [10].Lemma 3.7.
LetΔ be a finite prefix-suffix-free subset of
A*×A* and λ be a fuzzy language over A. Then the following are equivalent:(1)
PΔ,λ is of finite index.(2)
The following fuzzy languageλΔ over A defined by (3.13)λΔ(w)=λ(w)forw∈N(Δ),λΔ(w)=0forw∉N(Δ) is regular.(3)
λ=λ1∪λ2, where λ1 is regular and λ2(w)=0 for any w in N(Δ).Proof.
(1)implies (2). Let x,y be in A*, (s,t) be in Δ and xPΔ,λy. Then for any u,v in A*, (su,vt) is in ΩΔ. Therefore, (3.14)s-1λt-1(uxv)=λ(suxvt)=λ(suyvt)=s-1λt-1(uyv), whence xPs-1λt-1y. Thus, (3.15)PΔ,λ⊆⋂(s,t)∈ΔPs-1λt-1. Now, if PΔ,λ is of finite index, then s-1λt-1 is regular for any (s,t) in Δ. Observe that (3.16)λΔ=⋃(s,t)∈Δ[s(s-1λt-1)]t, it follows that λΔ is regular from Lemma 2.2.
(2)implies (3). By (2), λΔ is regular. Let λ2 be the following fuzzy language over
A defined by (3.17)λ2(w)=0forw∈N(Δ),λ2(w)=λ(w)forw∉N(Δ). Then λ=λΔ∪λ2, as required.
(3)implies (1). If λ=λ1∪λ2 for some regular fuzzy language λ1 and a fuzzy language λ2 such that λ2(w)=0 for any w in N(Δ), then Pλ1 is of finite index and PΔ,λ2=A*×A*. Observe that (3.18)Pλ1⊆PΔ,λ1⊆PΔ,λ1∪λ2=PΔ,λ,PΔ,λ is of finite index.Remark 3.8.
In general, for a given finite prefix-suffix-free subset ofA*×A* and a fuzzy language λ over A, λ may be nonregular even if PΔ,λ is of finite index. For example, let
A={a,b} and Δ={(a,b)}. Define the following fuzzy language
λ over A as follows: (3.19)λ(w)=0forw∈N(Δ),λ(w)=1|w|+1forw∉N(Δ). Clearly, λΔ(w)=0 for every w in A* and so λΔ is trivially regular. By Lemma 3.7, PΔ,λ is of finite index. However, for any pair
w1,w2 in N(Δ)¯ with different lengths, we have λ(w1)≠λ(w2) whence w1 is not Pλ related to w2. Observe that N(Δ)¯ is infinite, there are infinite Pλ-classes of A* and so Pλ is of infinite index. This implies that
λ is nonregular by Theorem 2.1.Now, we have our main theorem.Theorem 3.9 (An extended version of Myhill-Nerode theorem).
For a fuzzy languageλ over A, the following statements are equivalent:(1)
λ is regular.(2)
PS,λ(r) is of finite index for some finite maximal
suffix-free language S over A.(3)
PP,λ(l) is of finite index for some finite maximal
prefix-free language P over A.(4)
PΔ,λ is of finite index for some finite prefix-suffix-free
subset Δ of A*×A* such that N(Δ) is cofinite.(5)
Pℱ,P,λ(l) is of finite index for some finite maximal
prefix-free language P over A.(6)
Pℱ,S,λ(r) is of finite index for some finite maximal
suffix-free language S over A.Proof.
(1)implies (2). Observe that {1} is a maximal suffix-free language over
A and Pλ(r)=P{1},λ(r), the result follows from Theorem 2.1.
(2)implies (4). Observe that {1}×S is a prefix-suffix-free subset of A*×A* and N({1}×S)=A*S, the result follows from Lemma 3.5 (1) and Lemma 3.6.
(4) implies (1). By Lemma3.7 (3), there
exists a regular fuzzy language λ1 and another fuzzy language λ2 such that λ=λ1∪λ2 and λ2(w)=0 for any w in N(Δ). However, by (4), N(Δ)¯ is finite, which implies that λ2 is also regular. In view of Lemma 2.2, λ is regular.
By symmetry, we can prove that the facts that (1) implies (3) and (3) implies (4). On the
other hand, by Lemma3.5 (2) and its dual,
it follows that (3) is equivalent to (5) and (2) is equivalent to (6).


## 4. Conclusions

In this short note, we have obtained an extended version of Myhill-Nerode theorem for
fuzzy languages (Theorem3.9) which provides
some algebraic characterizations of regular fuzzy languages. On the other hand, for a given
prefix-suffix-free subset Δ of A*×A*, by Proposition 3.1 and Remark 3.8,
(4.1)FRΔ(A)={λ∣λisafuzzylanguageoverAsuchthattheindexofPΔ,λisfinite}contains the class of regular fuzzy languages overA as a proper subclass. In fact, Lemma 3.7 gives some characterizations of members in
𝔽ℝΔ(A) for a given finite prefix-suffix-free subset
Δ of A*×A*. Thus the following questions could be considered as a future
work. For a general prefix-suffix-free subset Δ of A*×A*, what can be said about 𝔽ℝΔ(A)? For example, can we obtain some results parallel to
Theorems  3.5 and 3.17 in [10]?



---

*Source: 804623-2012-09-02.xml*