A Remark on Myhill-Nerode Theorem for Fuzzy Languages

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)

  $$ is of finite index.

• (4)

  $$ is of finite index.

Lemma 2.2 (see [6].)Finite unions, intersections, products, and left-right quotients of regular fuzzy languages over A are regular.

Proposition 3.1. The above $$ are right congruences (resp., left congruences; congruence) on A^*. Furthermore,

Proof. It is easy to check that $$ (resp., $$) is a right (resp., left) congruence, P_Δ,λ is a congruence, and

by their definitions. In the sequel, we show that $$ is a right congruence and $$ is a left congruence. Clearly, both $$ and $$ are equivalences. Now, let x, y be two words in A^* and $$. Then there exists a finite subset F of A^* such that λ(xu) = λ(yu) for any u in $$. Now, let z be a word in A^* and F^′ be the union of {w ∈ A^*∣zw ∈ F} and {1}. Then zu is in $$ for any u in $$. This implies that λ(xzu) = λ(yzu) for any u in $$ whence $$ since F^′ is finite. Thus, $$ is a right congruence. Dually, $$ is a left congruence.

Remark 3.2. Note that the above inclusions are all proper in general. For example, let A = {a},   S = {a²} and F = {1, a, a², a³}. Then $$. Define a fuzzy language over A as follows:

where α, β are in [0,1] and α ≠ β. Then we have Similarly, we can show that the remainder inclusions are all proper.

Lemma 3.3. Let L be an infinite prefix-closed language over A. Then there exists an infinite subset {1, a₁, a₁a₂, …, a₁a₂, …, a_n, …} of L, where a_i ∈ A.

Proof. Denote

Observe that A is finite and L is infinite, there exists L₁⊆L and a₁ ∈ A such that L₁ is infinite and Pref_A(L₁) = {a₁}. Denote Then $$ is infinite. Hence, there also exists $$ and a₂ ∈ A such that L₂ is infinite and Pref_A(L₂) = {a₂}. In general, for any positive integer n, there exists $$ and a_n+1 ∈ A such that L_n+1 is infinite and Pref_A(L_n+1) = {a_n+1}. Let Clearly, C is infinite. We claim that C⊆L. Let a₁a₂a₃ ⋯ a_n ∈ C. Observe that Therefore, there exists y ∈ A^* such that a_ny ∈ (a₁a₂ ⋯ a_n−1) ⁻¹L₁. And hence, a₁a₂ ⋯ a_n−1a_ny ∈ L₁⊆L. Since L is prefix-closed, a₁a₂ ⋯ a_n−1a_n ∈ L. This implies that C⊆L.

Lemma 3.4. Let ρ be a right congruence on A^* and {L_i∣i ∈ I} be the set of all ρ-classes of A^*. Then,

is prefix-closed.

Proof. Clearly, 1 is in L_ρ. Let s_j be in L_ρ and s_j = a₁a₂ ⋯ a_t for some positive integer t > 1 and a₁, a₂, …, a_t in A. Then, a₁a₂ ⋯ a_t−1 is not in L_j. Suppose that a₁a₂ ⋯ a_t−1 is in L_k. Then, s_k ≤ a₁a₂ ⋯ a_t−1. This implies that s_ka_t ≤ a₁a₂ ⋯ a_t−1a_t = s_j. On the other hand, since s_kρa₁a₂ ⋯ a_t−1 and ρ is a right congruence, we have s_ka_tρs_j. Hence, s_ka_t is in L_j and so s_ka_t ≥ s_j. Thus, s_ka_t = s_j = a₁a₂a₃ ⋯ a_t−1a_t. This implies that s_k = a₁a₂a₃ ⋯ a_t−1 whence a₁a₂a₃ ⋯ a_t−1 is in L_ρ.

Lemma 3.5. Let S be a suffix-free language and λ be a fuzzy language over A.

• (1)

  P_{1}×S,λ is of finite index if and only if $$ is of finite index.

• (2)

  $$ is of finite index if and only if $$ is of finite index.

Proof. (1)  Similar to the proof of Proposition  3.11 in [10].

(2) Observe that $$, the necessity holds. Conversely, if $$ is of finite index and $$ is of infinite index, then by Lemma 3.4, $$ is infinite and prefix-closed. By Lemma 3.3, there exists an infinite subset

of $$, where a_i ∈ A. Since $$ is of finite index, there exist two distinct elements x, y ∈ C such that $$. Therefore, there exists a finite subset F of A^* such that $$. Denote T = max   {|f|∣f ∈ F} and take u in A^* satisfying |u | > T. We assert that uv is in $$ for any v in A^*S. In fact, if uv = fw for some f in F and w in $$, 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 $$.

Without loss of generality, we let x < y with respect to the alphabetic order, y = a₁a₂ ⋯ a_t and u = a_t+1 ⋯ a_t+T+1. Then, by the above discussions, $$ and yu is in C. Observe that C is a subset of $$, in view of the definition of $$, xu ≥ yu. This implies that x ≥ y. A contradiction.

Lemma 3.6. Let S 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

  $$ ()
  is regular.

• (3)

  λ = λ₁ ∪ λ₂, where λ₁ is regular and λ₂(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,

whence $$. Thus, Now, if P_Δ,λ is of finite index, then s⁻¹λt⁻¹ is regular for any (s, t) in Δ. Observe that it follows that λ_Δ is regular from Lemma 2.2.

(2) implies (3). By (2), λ_Δ is regular. Let λ₂ be the following fuzzy language over A defined by

Then λ = λ_Δ ∪ λ₂, as required.

(3) implies (1). If λ = λ₁ ∪ λ₂ for some regular fuzzy language λ₁ and a fuzzy language λ₂ such that λ₂(w) = 0 for any w in N(Δ), then $$ is of finite index and $$. Observe that

P_Δ,λ is of finite index.

Remark 3.8. In general, for a given finite prefix-suffix-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 λ over A as follows:

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 w₁, w₂ in $$ with different lengths, we have λ(w₁) ≠ λ(w₂) whence w₁ is not P_λ related to w₂. Observe that $$ 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.

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)

  $$ is of finite index for some finite maximal suffix-free language S over A.

• (3)

  $$ 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)

  $$ is of finite index for some finite maximal prefix-free language P over A.

• (6)

  $$ 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 $$, 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 Lemma 3.7 (3), there exists a regular fuzzy language λ₁ and another fuzzy language λ₂ such that λ = λ₁ ∪ λ₂ and λ₂(w) = 0 for any w in N(Δ). However, by (4), $$ is finite, which implies that λ₂ 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 Lemma 3.5 (2) and its dual, it follows that (3) is equivalent to (5) and (2) is equivalent to (6).