A Remark on Myhill-Nerode Theorem for Fuzzy Languages

(1)

Journal of Applied Mathematics Volume 2012, Article ID 804623,9pages doi:10.1155/2012/804623

Research Article

A Remark on Myhill-Nerode Theorem for Fuzzy Languages

Shou-feng Wang

School of Mathematics, Yunnan Normal University, Yunnan, Kunming 650500, China

Correspondence should be addressed to Shou-feng Wang,[email protected] Received 21 May 2012; Accepted 4 August 2012

Academic Editor: Abdel-Maksoud A. Soliman

Copyrightq2012 Shou-feng Wang. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

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

1. Introduction

Fuzzy sets were introduced by Zadeh in1and since then have appeared in many fields of sciences. They have been studied within automata theory for the first time by Wee in2. More on recent development of algebraic theory of fuzzy automata and formal fuzzy languages can be found in the book Mordeson and Malik3, the texts Malik et al.4,5, and Petkovi´c6.

A fuzzy language is called regular if it can be recognized by a fuzzy automaton. In the texts Mordeson and Malik3, Petkovi´c6, Ignjatovic et al.7, and Shen8, regular fuzzy languages have been characterized by the principal congruencesprincipal right congruences, principal left congruencesdetermined by fuzzy languages, which are known as Myhill-Nerode theorem for fuzzy languages. Moreover, Petkovi´c 6 also considered the varieties of fuzzy languages and Ignjatovic and Ciric9considered regular operations of fuzzy languages.

Recently, Wang et al.10generalized the usual principal congruencesresp., principal right congruences, principal left congruencesto some kinds of generalized principal congru- encesresp., generalized principal right congruences, generalized principal left congruencesdeter- mined by crisp languages by using prefix-suﬃx-free subsetsresp., prefix-free languages, suﬃx- free languagesand obtained some characterizations of regular crisp languages.

In this note, we will realize the idea of the text10for 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

(2)

determined by fuzzy languages. In particular, we obtain an extended version of Myhill- Nerode theorem for fuzzy languages.

2. Preliminaries

Throughout the paper,Ais a finite set which is called an alphabet andA^∗is the free monoid generated byA, that is, the set of all words with letters fromA. The empty word is denoted by 1. The length of a wordwinA^∗ is the number of letters appearing inw and is denoted by|w|. The complement of a subsetL ofA^∗is the setL {w ∈ A^∗ | w /∈ L}. A subsetL of A^∗is cofinite ifLis finite. A nonempty subsetSofA^∗ is called a suﬃx-free language overAif no element inSis a suﬃx of another element inS. Prefix-free languages overAcan be defined dually. On the other hand, a nonempty subsetLofA^∗is called a prefix-closed language overA if any prefix of an element inLis also inL.

As an analogue of prefix-free languages and suﬃx-free languages overA, Wang et al.

10introduced prefix-suﬃx-free subsets ofA^∗ ×A^∗. A subset Δof the setA^∗ ×A^∗ is called a prefix-suﬃx-free subset if for all wordss, t, x, yinA^∗, the following holds: if boths, tand sx, ytare inΔ, thenxy1.

An equivalenceρonA^∗is called a right congruence ifxρyimplies thatxzρyzfor 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.

A fuzzy subsetα of a setX is a mappingα : X → 0,1. By∧and ∨ infimum and supremum in the unit segment0,1will be denoted, respectively. Every elementyofXcan be considered as the following fuzzy subset ofX:

yx 1 forxy, yx 0 for x /y. 2.1

A fuzzy language overAis a fuzzy subset ofA^∗. A fuzzy language is regular if it is recognizable by a fuzzy automaton from the book3. For a fuzzy languageλoverA, the relations defined onA^∗by the following:

xP_λ^ryif λxu λ yu

for everyuinA^∗, xP_λ^ly ifλux λ

uy

for everyuinA^∗, xPλyif λuxv λ

uyv

for everyu, v∈A^∗,

2.2

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 that the index of an equivalenceρonA^∗is the number ofρ-classes ofA^∗.

Theorem 2.1see3,6,8, Myhill-Nerode theorem. For a fuzzy languageλoverA, the following statements are equivalent:

1λ is regular.

2P_λis of finite index.

(3)

3P_λ^ris of finite index.

4P_λ^lis of finite index.

In the sequel, we recall some operations of fuzzy languages. For two fuzzy languages λ1 andλ2 overA, the union, intersection, product, and left and right quotients ofλ1 andλ2are defined, respectively, by the following:

λ1∪λ2w λ1w∨λ2w, λ1∩λ2w λ1w∧λ2w, λ1λ2w

xyw

λ1x∧λ2

y

λ⁻¹₁ λ2

w

u∈A^∗

λ2uw∧λ1u, λ2λ⁻¹₁

w

u∈A^∗

λ2wu∧λ1u.

2.3

Further, we also define left-right quotient of three fuzzy languagesλ1,λ2andλoverAby the following:

λ⁻¹₁ λλ⁻¹₂

w λ⁻¹₁ λ

λ⁻¹₂

w. 2.4

Observe thats⁻¹λt⁻¹w λswtfor anys, t, w∈A^∗with the above notations.

On regular fuzzy languages, we have the following.

Lemma 2.2see6. Finite unions, intersections, products, and left-right quotients of regular fuzzy languages overAare 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-suﬃx-free subsetsresp., prefix- free languages, suﬃx-free languages and give an extended version of Myhill-Nerode theorem for fuzzy languages.

Now, letPbe a prefix-free language,Sbe a suffix-free language overA,Δbe a prefix- suffix-free subset ofA^∗×A^∗, andλ be a fuzzy language overA, respectively. For a prefix- suffix-free subsetΔ, denote

Ω_Δ sx, yt

|s, t∈Δ, x, y∈A^∗

, NΔ

s,t∈Δ

sA^∗t. 3.1

(4)

Define the following relations onA^∗:

xP_P,λ^lyifλux λ uy

for everyuinPA^∗, xP_S,λ^ryif λxu λ

yu

for everyuinA^∗S, xP_Δ,λyif λuxv λ

uyv

for everyu, vinΩ_Δ, xP_F,S,λ^r yif there exists some finite subsetF of A^∗such that

λxu λ yu

for everyuinFA^∗S,

xP_F,P,λ^l yif there exists some finite subset F ofA^∗such that λux λ

uy

for everyuinPA^∗F.

3.2

Then we have the following observations.

Proposition 3.1. The aboveP_S,λ^r, P_F,S,λ^r resp.,P_P,λ^l, P_F,P,λ^l ; P_Δ,λ are right congruences (resp., left congruences; congruence) onA^∗. Furthermore,

P_λ^r⊆P_S,λ^r⊆P_F,S,λ^r , P_λ^l ⊆P_P,λ^l ⊆P_F,P,λ^l , P_λ⊆P_Δ,λ. 3.3

Proof. It is easy to check that P_S,λ^r resp.,P_P,λ^l is a right resp., left congruence, PΔ,λ is a congruence, and

P_λ^r⊆P_S,λ^r⊆P_F,S,λ^r , P_λ^l⊆P_P,λ^l ⊆P_F,P,λ^l , Pλ⊆PΔ,λ 3.4

by their definitions. In the sequel, we show thatP_F,S,λ^r is a right congruence and P_F,P,λ^l is a left congruence. Clearly, bothP_F,S,λ^r andP_F,P,λ^l are equivalences. Now, letx, ybe two words inA^∗andxP_F,S,λ^r y. Then there exists a finite subsetFofA^∗such thatλxu λyufor any uinFA^∗S. Now, letzbe a word inA^∗ andFbe the union of{w ∈ A^∗ | zw ∈F}and{1}.

Thenzuis inFA^∗Sfor anyuinFA^∗S. This implies thatλxzu λyzufor anyuinFA^∗S whencexzP_F,S,λ^r yzsinceFis finite. Thus,P_F,S,λ^r is a right congruence. Dually,P_F,P,λ^l is a left congruence.

Remark 3.2. Note that the above inclusions are all proper in general. For example, let A {a}, S{a²}andF {1, a, a², a³}. ThenFA^∗S A^∗a⁵. Define a fuzzy language overAas follows:

λw α forw∈ a², a³

, λw β forw∈A^∗\ a², a³

, 3.5

(5)

whereα, βare in0,1andα /β. Then we have a³, a⁴

/

∈P_λ^r, a³, a⁴

∈P_S,λ^r, 1, a²

/

∈P_S,λ^r, 1, a²

∈P_F,S,λ^r . 3.6

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 following alphabetic order “≤” on A^∗: For two words u and v in A^∗ with diﬀerent 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 onA^∗. We have the following result.

Lemma 3.3. LetLbe an infinite prefix-closed language overA. Then there exists an infinite subset {1, a1, a1a2, . . . , a1a2, . . . , a_n, . . .}ofL, wherea_i∈A.

Proof. Denote

Pref_AL a∈A|

∃y∈A^∗

ay∈L

. 3.7

Observe thatAis finite andLis infinite, there existsL1⊆Landa1∈Asuch thatL1is infinite and Pref_AL1 {a1}. Denote

a⁻¹₁ L1{w∈A^∗|a1w∈L1}. 3.8

Thena⁻¹₁ L1is infinite. Hence, there also existsL2 ⊆a⁻¹₁ L1anda2 ∈Asuch thatL2 is infinite and Pref_AL2 {a2}. In general, for any positive integern, there existsLn1 ⊆ a⁻¹_n Lnand a_n1∈Asuch thatL_n1is infinite and Pref_AL_n1 {a_n1}. Let

C{1, a1, a1a2, a1a2a3, . . . , a1a2a3· · ·an, . . .}. 3.9

Clearly,Cis infinite. We claim thatC⊆L. Leta1a2a3· · ·an∈C. Observe that L_n ⊆a⁻¹_n−1L_n−1⊆a⁻¹_n−1a⁻¹_n−2L_n−2⊆ · · · ⊆a⁻¹_n−1a⁻¹_n−2· · ·a⁻¹₁ L1 a1a2· · ·a_n−1⁻¹L1,

{an}Pref_ALn⊆Pref_A

a1a2· · ·an−1⁻¹L1

. 3.10

Therefore, there exists y ∈ A^∗ such that any ∈ a1a2· · ·an−1⁻¹L1. And hence, a1a2· · ·an−1any ∈ L1 ⊆ L. SinceL is prefix-closed, a1a2· · ·an−1an ∈ L. This implies that C⊆L.

Lemma 3.4. Letρbe a right congruence onA^∗and{Li|i∈I}be the set of allρ-classes ofA^∗. Then, L_ρ{s_i|s_i is the least element inL_i with respect to “≤”, i∈I} 3.11

is prefix-closed.

(6)

Proof. Clearly, 1 is inLρ. Letsjbe inLρandsja1a2· · ·atfor some positive integert >1 and a1, a2, . . . , a_t in A. Then, a1a2· · ·a_t−1 is not in L_j. Suppose that a1a2· · ·a_t−1 is inL_k. 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 inLj and so s_ka_t ≥ s_j. Thus,s_ka_t s_j a1a2a3· · ·a_t−1a_t. This implies thats_k a1a2a3· · ·a_t−1 whence a1a2a3· · ·a_t−1is inL_ρ.

Lemma 3.5. LetSbe a suﬃx-free language andλbe a fuzzy language overA.

1P{1}×S,λis of finite index if and only ifP_S,λ^ris of finite index.

2P_S,λ^ris of finite index if and only ifP_F,S,λ^r is of finite index.

Proof. 1Similar to the proof of Proposition 3.11 in10.

2 Observe that P_S,λ^r ⊆ P_F,S,λ^r , the necessity holds. Conversely, if P_F,S,λ^r is of finite index andP_S,λ^r is of infinite index, then byLemma 3.4,L_P^r

S,λ is infinite and prefix-closed. By Lemma 3.3, there exists an infinite subset

C{1, a1, a1a2,· · · , a1a2· · ·an, . . .}, 3.12 of L_P^r

S,λ, where ai ∈ A. Since P_F,S,λ^r is of finite index, there exist two distinct elements x, y ∈ Csuch thatxP_F,S,λ^r y. Therefore, there exists a finite subsetF ofA^∗such thatλxu λyufor everyuinFA^∗S. DenoteT max{|f| |f ∈F}and takeuinA^∗satisfying|u|> T. We assert thatuvis inFA^∗Sfor anyvinA^∗S. In fact, ifuv fwfor somef inF andw in A^∗S, then by the choice ofu,f is a prefix ofuand sovis a suﬃx ofwwhencewis inA^∗S.

A contradiction. Therefore, for anyvinA^∗S, we haveλxuv λyuv. This implies that xuP_S,λ^ryu.

Without loss of generality, we let x < y with respect to the alphabetic order, y a1a2· · ·a_tand u a_t1· · ·a_tT1. Then, by the above discussions, xuP_S,λ^ryuand yuis inC.

Observe thatCis a subset ofL_P^r

S,λ, in view of the definition ofL_P^r

S,λ,xu≥yu. This implies that x≥y. A contradiction.

Lemma 3.6. LetS be a finite suﬃx-free language overA. ThenA^∗S is cofinite if and only ifS is maximal.

Proof. It follows from Lemma 3.14 in10.

Lemma 3.7. LetΔbe a finite prefix-suﬃx-free subset ofA^∗×A^∗andλbe a fuzzy language overA.

Then the following are equivalent:

1PΔ,λis of finite index.

2The following fuzzy languageλΔoverAdefined by

λΔw λw forw∈NΔ, λΔw 0 forw /∈NΔ 3.13

is regular.

3λλ1∪λ2, whereλ1is regular andλ2w 0 for anywinNΔ.

(7)

Proof. 1 implies 2. Letx, y be in A^∗,s, tbe in Δand xPΔ,λy. Then for any u, v inA^∗, su, vtis inΩ_Δ. Therefore,

s⁻¹λt⁻¹uxv λsuxvt λ suyvt

s⁻¹λt⁻¹ uyv

, 3.14

whencexP_s⁻¹_λt⁻¹y. Thus,

P_Δ,λ⊆

s,t∈Δ

P_s⁻¹_λt⁻¹. 3.15

Now, ifP_Δ,λis of finite index, thens⁻¹λt⁻¹is regular for anys, tinΔ. Observe that

λ_Δ

s,t∈Δ

s

s⁻¹λt⁻¹

t, 3.16

it follows thatλΔis regular fromLemma 2.2.

2 implies3. By 2,λ_Δ is regular. Let λ2 be the following fuzzy language over A defined by

λ2w 0 for w∈NΔ, λ2w λw forw /∈NΔ. 3.17

ThenλλΔ∪λ2, as required.

3implies1. Ifλλ1∪λ2for some regular fuzzy languageλ1and a fuzzy language λ2 such thatλ2w 0 for anyw inNΔ, thenP_λ₁ is of finite index andP_Δ,λ₂ A^∗×A^∗. Observe that

Pλ1⊆PΔ,λ1⊆PΔ,λ1∪λ2PΔ,λ, 3.18

P_Δ,λis of finite index.

Remark 3.8. In general, for a given finite prefix-suﬃx-free subset of A^∗ ×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λoverAas follows:

λw 0 for w∈NΔ, λw 1

|w|1 forw /∈NΔ. 3.19

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 diﬀerent lengths, we have λw1/λw2 whence w1 is not P_λ related tow2. Observe that NΔis infinite, there are infiniteP_λ-classes ofA^∗ and soP_λis of infinite index. This implies thatλ is nonregular by Theorem 2.1.

Now, we have our main theorem.

(8)

Theorem 3.9An extended version of Myhill-Nerode theorem. For a fuzzy languageλoverA, the following statements are equivalent:

1λis regular.

2P_S,λ^ris of finite index for some finite maximal suﬃx-free languageSoverA.

3P_P,λ^l is of finite index for some finite maximal prefix-free languagePoverA.

4PΔ,λis of finite index for some finite prefix-suﬃx-free subsetΔofA^∗×A^∗such thatNΔ is cofinite.

5P_F,P,λ^l is of finite index for some finite maximal prefix-free languageP overA.

6P_F,S,λ^r is of finite index for some finite maximal suﬃx-free languageSoverA.

Proof. 1implies2. Observe that{1}is a maximal suﬃx-free language overAand P_λ^r P_{1},λ^r , the result follows fromTheorem 2.1.

2implies4. Observe that{1}×Sis a prefix-suﬃx-free subset ofA^∗×A^∗andN{1}×

S A^∗S, the result follows fromLemma 3.51andLemma 3.6.

4implies1. ByLemma 3.73, there exists a regular fuzzy languageλ1and another fuzzy languageλ2such thatλλ1∪λ2andλ2w 0 for anywinNΔ. However, by4, NΔis finite, which implies thatλ2is also regular. In view ofLemma 2.2,λis regular.

By symmetry, we can prove that the facts that1implies3and3implies4. On the other hand, byLemma 3.52and its dual, it follows that3is equivalent to5and2 is equivalent to6.

4. Conclusions

In this short note, we have obtained an extended version of Myhill-Nerode theorem for fuzzy languagesTheorem 3.9which provides some algebraic characterizations of regular fuzzy languages. On the other hand, for a given prefix-suﬃx-free subsetΔof A^∗×A^∗, by Proposition 3.1andRemark 3.8,

FR_ΔA λ|λis a fuzzy language overAsuch that the index ofP_Δ,λ is finite 4.1 contains the class of regular fuzzy languages over A as a proper subclass. In fact, Lemma 3.7 gives some characterizations of members in FRΔA for a given finite prefix- suﬃx-free subsetΔofA^∗×A^∗. Thus the following questions could be considered as a future work. For a general prefix-suﬃx-free subsetΔofA^∗×A^∗, what can be said aboutFRΔA?

For example, can we obtain some results parallel to Theorems 3.5 and 3.17 in10?

References

1 L. A. Zadeh, “Fuzzy sets,” Information and Computation, vol. 8, pp. 338–353, 1965.

2 W. G. Wee, On generalizations of adaptive algorithm and application of the fuzzy sets concept to pattern classification, [Ph.D. thesis], Purdue University, 1967.

3 J. N. Mordeson and D. S. Malik, Fuzzy Automata and Languages, Chapman & Hall/CRC, 2002.

4 D. S. Malik, J. N. Mordeson, and M. K. Sen, “Products of fuzzy finite state machines,” Fuzzy Sets and Systems, vol. 92, no. 1, pp. 95–102, 1997.

(9)

5 D. S. Malik, J. N. Mordeson, and M. K. Sen, “Minimization of fuzzy finite automata,” Information Sciences, vol. 113, no. 3-4, pp. 323–330, 1999.

6 T. Petkovi´c, “Varieties of fuzzy languages,” in Proceedings of the 1st International Conference on Algebraic Informatics, pp. 197–205, Aristotle University of Thessaloniki, Thessaloniki, Greece, 2005.

7 J. Ignjatovic, M. Ciric, S. Bogdanovic, and T. Petkovic, “Myhill-Nerode type theory for fuzzy lang- uages and automata,” Fuzzy Sets and Systems, vol. 161, no. 9, pp. 1288–1324, 2010.

8 J. Shen, “Fuzzy language on free monoid,” Information Sciences, vol. 88, no. 1–4, pp. 149–168, 1996.

9 J. Ignjatovic and M. Ciric, “Formal power series and regular operations on fuzzy languages,”

Information Sciences, vol. 180, no. 7, pp. 1104–1120, 2010.

10 S. F. Wang, Y. Q. Guo, and S. X. Xu, “PS-regular languages,” International Journal of Computer Mathematics, vol. 88, no. 12, pp. 2464–2484, 2011.

(10)

Submit your manuscripts at http://www.hindawi.com

Hindawi Publishing Corporation

http://www.hindawi.com Volume 2014

Mathematics

^{Journal of}

Hindawi Publishing Corporation http://www.hindawi.com

Differential Equations

International Journal of

Volume 2014

Applied Mathematics^{Journal of}

Mathematical PhysicsAdvances in

Complex Analysis

^{Journal of}

Optimization

^{Journal of}

Combinatorics

Journal of

Function Spaces

Abstract and Applied Analysis

International Journal of Mathematics and Mathematical Sciences

The Scientific World Journal

Discrete Dynamics in Nature and Society

Discrete Mathematics

^{Journal of}

A Remark on Myhill-Nerode Theorem for Fuzzy Languages

Research Article