Conversion of fuzzy automata into fuzzy regular expressions using transitive closure

Abstract

The concept of transitive closure is useful for the conversion of classical finite automata into regular expressions. In this paper, we generalize and extend the concept of transitive closure for the conversion of fuzzy automata into fuzzy regular expressions. We prove that, for a fuzzy automaton M where r is a fuzzy regular expression obtained using the proposed approach, L(M)=L(r). Finally, a numerical example illustrates this conversion.

Keywords

Fuzzy regular expression fuzzy automata integral lattice monoid transitive closure

1 Introduction

The importance of regular expressions and finite automata is well known. The notion of fuzzy automata was first proposed in 1968 by Santos [9]. Regular expressions involving imprecision and vagueness are known as fuzzy regular expressions. They are widely used in various applications, such as control systems, databases, clinical monitoring, computing with words, pattern recognition, learning systems, discrete event systems, and descriptions of natural and programming languages [1 , 27]. Fuzzy automata are a generalization of classical automata, closing the gap between classical automata theory and natural languages.

Zadeh [19] proposed the concept of fuzzy set theory in 1965. Wee and Fu [27] proposed the mathematical formulation of fuzzy automata. Mordeson and Malik [15] introduced the modern view of fuzzy automata and languages. To enhance the processing ability of fuzzy automata, membership values are extended to algebraic structures, such as lattice-ordered monoids [28, 30], complete residuated lattices [3], and other types of lattices. Li and Pedrycz [30] proved that fuzzy languages over an integral lattice-ordered monoid can be described using fuzzy regular expressions if and only if fuzzy finite automata can be designed for them.

Cao and Ezawa [4] introduced the concept of non-deterministic fuzzy automata and further proved that non-deterministic finite automata, non-deterministic finite automata with ɛ-moves, and deterministic finite automata are equivalent. A fuzzy automaton is an instance of weighted automata [21] with values taken from a lattice-ordered monoid rather than a more general semiring structure. Li [29] investigated the membership values of finite automata in a lattice to present a minimization algorithm for lattice-valued finite automata.

Several approaches for converting fuzzy regular expressions into fuzzy automata have been proposed in the literature. Stamenković and Ćirić [3] proposed an elegant method for the conversion of fuzzy regular expressions into fuzzy automata based on the concept of a position automaton. Similarly, Mendivil and Garitagoitia [16] described a method for constructing a fuzzy automaton with ɛ-moves from fuzzy regular expressions. Kumar and Kumar [23, 24] outlined a method for the conversion of fuzzy regular expressions into fuzzy automata based on the follow automata [20].

The literature describes various methods for converting deterministic finite automata into regular expressions (see refs [5 , 25]). The most widely used constructions are transitive closure [14], state elimination [6], and Brzozowski algebraic methods [13]. In this paper, we propose an algorithm for the conversion of a fuzzy automaton into a fuzzy regular expression by extending the well-known concept of the transitive closure method [14] used for the conversion of deterministic finite automata into regular expressions.

The content of this paper is organized as follows. In Section 2, we briefly review lattice-ordered monoids, fuzzy regular expressions, and fuzzy automata. In Section 3, we describe a construction for the conversion of fuzzy automata into fuzzy regular expressions using the transitive closure method and establish the equivalence of fuzzy automata and fuzzy regular expressions. We provide a numerical example in support of our results in Section 4, with concluding remarks given in Section 5.

2 Preliminary concepts

This section is devoted to recalling basic concepts and notations used in the area of fuzzy automata. If we let X be an alphabet consisting of a finite set of symbols or letters, then X^* is the free monoid equipped with the concatenation operation including the empty / null string (denoted by ɛ). A fuzzy language over X is a fuzzy subset of X^*. In this paper, we use the concept of integral ℓ-monoid (L, ∧ , ∨ , ⊗ , 0, 1) for the formulation of fuzzy automata. Every word x ∈ X^* has a degree of membership value in f given by f (x) ∈ L [4].

Definition 2.1: A lattice-ordered monoid or ℓ-monoid [3] (L, ∧ , ∨ , ⊗ , 0, 1) such that

(L, ∧ , ∨) is a lattice with least element 0 and greatest element 1.

(L, ⊗ , e) is a monoid with the unit element e.

For ∀x, y, z ∈ L,

\begin{matrix} x \otimes (y \lor z) = x \otimes y \lor x \otimes z \end{matrix}

(1a)

\begin{matrix} (x \lor y) \otimes z = x \otimes z \lor y \otimes z \end{matrix}

(1b)

For ∀x ∈ L, x ⊗ 0 =0 ⊗ x = 0

Definition 2.2: Integral ℓ-monoid [3] is a ℓ-monoid in which the unit element e and 1 coincide.

Definition 2.3: The family of fuzzy regular expression LR [30] over X is defined inductively as follows:

ɛ ∈ LR, (2a)

φ ∈ LR, (2b)

∀x ∈ X ; x ∈ LR, (2c)

∀λ ∈ L, r ∈ LR ; (λr) ∈ LR, (2d)

∀r₁, r₂ ∈ LR ; (r₁ + r₂) ∈ LR, (2e)

∀r₁, r₂ ∈ LR ; (r₁r₂) ∈ LR, (2f)

∀r ∈ LR ; (r^*) ∈ LR . (2g)

There are no other fuzzy regular expressions than those in Definition 2.3.

Definition 2.4: The fuzzy language ||r|| [30] represented by the fuzzy regular expression r ∈ LR can be defined as follows:

||φ||=0, (3a)

For x ∈ X ∪ {ɛ} ; ||x|| = {x/1} , (3b)

For λ ∈ L, r ∈ LR ; ||λr|| = λ ⊗ r, (3c)

r₁, r₂ ∈ LR ; ||r₁ + r₂|| = ||r₁|| + ||r₂||, (3d)

r₁, r₂ ∈ LR ; ||r₁r₂|| = ||r₁||||r₂||, (3e)

r ∈ LR ; ||r^*|| = ||r||^* . (3f)

Definition 2.5: A fuzzy automaton M [4, 16] is a quintuple (Q, X, δ, σ, τ) where Q is a finite non-empty set of states, X is an alphabet, δ is a fuzzy subset of a fuzzy transition relation (Q × X × Q), σ represents initial fuzzy states and is a fuzzy subset of Q, and τ represents final fuzzy states and is a fuzzy subset of Q.

Definition 2.6: The fuzzy language L (M) [16] accepted by the fuzzy automaton M is defined by

For any word x ∈ X^*, x = x₁x₂ … x_n, ∃ x_i ∈ X

$L (M) (x) = σ \circ δ_{x_{1}} \circ δ_{x_{2}} \circ \dots \circ δ_{x_{n}} \circ τ$ (4)

Using composition operator on fuzzy relations [16] $\begin{matrix} L (M) (x) = \lor σ (q_{0}) \otimes δ_{x_{1}} (q_{0}, q_{1}) \otimes δ_{x_{2}} (q_{1}, q_{2}) \otimes \dots \\ \otimes δ_{x_{n}} (q_{n - 1}, q_{n}) \otimes τ (q_{n}) \end{matrix}$ (5)

For empty string $L (M) (x) = σ \circ τ = \lor (σ (q_{0}) \otimes τ (q_{0}))$ (6)

3 Fuzzy finite automata to fuzzy regular expressions using transitive closure

In this section, we use the transitive closure method for the conversion of fuzzy automata into fuzzy regular expressions. We consider the Kleene closure to have highest priority in a fuzzy regular expression, followed by concatenation and then addition or scalar. The algorithm FA _ FRE (M, r) converts a fuzzy automaton into a fuzzy regular expression.

Theorem 1:Given a fuzzy automatonM = (Q, X, δ, σ, τ), there exists a fuzzy regular expressionrobtained fromMusing the algorithmFA _ FRE (M, r) such thatL (M) = L (r).

Proof: Let |Q| = n. Rename the state names of M to the first n positive numbers {1, 2, …, n}. This theorem is established by starting with k = 0 and finally reaching k = n [14].

$R_{ij}^{k}$ denotes the fuzzy regular expressions using the path from state i to state j such that no intermediate node in the path is greater than k.

Basis step: Consider that k = 0 means that no intermediate states are presenting.

For ∃i, j ∈ n, initialize $R_{ij}^{0} = φ$

For each transition from state i to state j, the following three cases can occur:

Case 1: If there exists only one symbol a from state i to state j with membership value λ as delineated in Fig. 1, then $R_{ij}^{0} = R_{ij}^{0} + λ a$ (7)

Case 2: If there are symbols a₁, a₂, …, a_l with respective memberships from state i to state j with membership values λ₁, λ₂, …, λ_l as delineated in Fig. 2, then $R_{ij}^{0} = R_{ij}^{0} + λ_{1} a_{1} + λ_{1} a_{2} + \dots + λ_{l} a_{l}$ (8)

Case 3: If i = j $R_{ij}^{0} = R_{ij}^{0} + λ ɛ where λ = 1$ (9)

Induction step: Now, we consider the path from state i to state j such that the intermediate state is not higher than k. The following two cases can occur:

Case 1: If there exists no new path from state i to state j using intermediate state k [14], then $R_{ij}^{k} = R_{ij}^{k - 1}$ (10)

Case 2: The path from state i to state j can go through the intermediate state k. The fuzzy regular expression $R_{ij}^{k}$ (as shown in Fig. 3) through intermediate state k can be found using $R_{ij}^{k} = R_{ik}^{k - 1} \otimes (R_{kk}^{k - 1} \otimes)^{*} R_{kj}^{k - 1}$ (11)

The first expression $R_{ik}^{k - 1}$ represents the fuzzy regular expression from state i to state k using an intermediate state from {1, 2, …, k - 1}.

The second expression $(R_{kk}^{k - 1})^{*}$ represents the fuzzy regular expression from state k to state k using an intermediate state from {1, 2, …, k - 1}.

The third expression $R_{kj}^{k - 1}$ represents the fuzzy regular expression from state k to state j using an intermediate state from {1, 2, …, k - 1}.

Hence R_{ij}^{k} = R_{ij}^{k - 1} + R_{ik}^{k - 1} \otimes (R_{kk}^{k - 1} \otimes)^{*} R_{kj}^{k - 1}

(12)

Consider that the starting state q₁ has the membership value and final state F = {q_l, q_m, …}. Consider the fuzzy membership value of the initial state to be σ (1).

The final fuzzy regular expression equivalent to the fuzzy automaton is as follows. $R = \cup_{i \in F} (σ (1) \otimes R_{1 i}^{n} \otimes τ (q_{i}))$ (13)

The proof of Theorem 1 is an enhancement of the transitive closure method [14] for the conversion of deterministic finite automata into regular expressions with the inclusion of the fuzziness concept. Further, we need to simplify the obtained intermediate fuzzy regular expressions at each iteration to obtain a smaller fuzzy regular expression.

4 Applications of the modified transitive closure method

In this section, the modified transitive closure method has been successfully applied to construct a fuzzy regular expression from the fuzzy automaton. This example is taken from [3, 16].

Example 1: Given the fuzzy automaton as shown in Fig. 4.

Final state with their membership values are {(P₁/0.2) , (P₃/1) , (P₄/1)}.

Initially k = 0, following are the initial fuzzy regular expressions:

Final state with their membership values are {(P₁/0.2) , (P₃/1) , (P₄/1)}. $\begin{matrix} R_{11}^{0} = 1.0 ɛ R_{21}^{0} = φ R_{31}^{0} = φ R_{41}^{0} = φ \\ R_{12}^{0} = 0.2 y R_{22}^{0} = 1.0 ɛ R_{32}^{0} = φ R_{42}^{0} = φ \\ R_{13}^{0} = 0.02 x R_{23}^{0} = φ R_{33}^{0} = 1.0 ɛ R_{43}^{0} = 1.0 x \\ R_{14}^{0} = φ R_{24}^{0} = φ R_{34}^{0} = 1.0 y R_{44}^{0} = 1.0 ɛ \\ R_{ij}^{k} = R_{ij}^{(k - 1)} + R_{ik}^{(k - 1)} (R_{kk}^{(k - 1)})^{*} R_{kj}^{(k - 1)} \end{matrix}$ (14) $\begin{matrix} k = 1 \\ R_{11}^{1} = R_{11}^{0} + R_{11}^{0} (R_{11}^{0})^{*} R_{11}^{0} \\ = 1.0 ɛ + 1.0 ɛ (1.0 ɛ)^{*} 1.0 ɛ = 1.0 ɛ \end{matrix}$ (15) $\begin{matrix} R_{12}^{1} = R_{12}^{0} + R_{11}^{0} (R_{11}^{0})^{*} R_{12}^{0} \\ = 0.2 y + 1.0 ɛ (1.0 ɛ)^{*} 0.2 y = 0.2 y \end{matrix}$ (16) $\begin{matrix} R_{13}^{1} = R_{13}^{0} + R_{11}^{0} (R_{11}^{0})^{*} R_{13}^{0} \\ = 0.02 x + 1.0 ɛ (1.0 ɛ)^{*} 0.02 x = 0.02 x \end{matrix}$ (17) $R_{14}^{1} = R_{14}^{0} + R_{11}^{0} (R_{11}^{0})^{*} R_{14}^{0} = φ$ (18) $R_{21}^{1} = R_{21}^{0} + R_{21}^{0} (R_{11}^{0})^{*} R_{11}^{0} = φ$ (19) $R_{22}^{1} = R_{22}^{0} + R_{21}^{0} (R_{11}^{0})^{*} R_{12}^{0} = 1.0 ɛ + φ = 1.0 ɛ$ (20) $R_{23}^{1} = R_{23}^{0} + R_{21}^{0} (R_{11}^{0})^{*} R_{13}^{0} = φ + φ = φ$ (21) $R_{24}^{1} = R_{24}^{0} + R_{21}^{0} (R_{11}^{0})^{*} R_{14}^{0} = φ + φ = φ$ (22) $R_{3 j}^{1} = R_{3 j}^{0} + R_{31}^{0} (R_{11}^{0})^{*} R_{1 j}^{0}$ (23) $R_{31}^{1} = R_{31}^{0} + R_{31}^{0} (R_{11}^{0})^{*} R_{11}^{0} = φ + φ = φ$ (24) $R_{32}^{1} = R_{32}^{0} + R_{31}^{0} (R_{11}^{0})^{*} R_{12}^{0} = φ + φ = φ$ (25) $R_{33}^{1} = R_{33}^{0} + R_{31}^{0} (R_{11}^{0})^{*} R_{13}^{0} = 1.0 ɛ$ (26) $R_{34}^{1} = R_{34}^{0} + R_{31}^{0} (R_{11}^{0})^{*} R_{14}^{0} = y + φ = y$ (27) $R_{4 j}^{1} = R_{4 j}^{0} + R_{41}^{0} (R_{11}^{0})^{*} R_{1 j}^{0} = R_{4 j}^{0}$ (28) $R_{41}^{1} = φ R_{42}^{1} = φ R_{43}^{1} = 1.0 x R_{44}^{1} = 1.0 ɛ$ (29) $\begin{matrix} R_{ij}^{k} = R_{ij}^{(k - 1)} + R_{ik}^{(k - 1)} (R_{kk}^{(k - 1)})^{*} R_{kj}^{(k - 1)} \\ k = 2 \end{matrix}$ (30) $R_{1 j}^{2} = R_{1 j}^{1} + R_{12}^{1} (R_{22}^{1})^{*} R_{2 j}^{1}$ (31) $R_{11}^{2} = R_{11}^{1} + R_{12}^{1} (R_{22}^{1})^{*} R_{21}^{1} = 1.0 ɛ + φ = 1.0 ɛ$ (32) $\begin{matrix} R_{12}^{2} = R_{12}^{1} + R_{12}^{1} (R_{22}^{1})^{*} R_{22}^{1} \\ = 0.2 y + 0.2 y (1.0 ɛ)^{*} 1.0 ɛ = 0.2 y \end{matrix}$ (33) $\begin{matrix} R_{13}^{2} = R_{13}^{1} + R_{12}^{1} (R_{22}^{1})^{*} R_{23}^{1} \\ = 0.02 x + φ = 0.02 x \end{matrix}$ (34) $R_{14}^{2} = R_{14}^{1} + R_{12}^{1} (R_{22}^{1})^{*} R_{24}^{1}$ (35) $\begin{matrix} = φ + 0.2 y (1.0 ɛ)^{*} φ = φ \\ R_{2 j}^{2} = R_{2 j}^{1} + R_{22}^{1} (R_{22}^{1})^{*} R_{2 j}^{1} \end{matrix}$ (36) $\begin{matrix} R_{21}^{2} = R_{21}^{1} + R_{22}^{1} (R_{22}^{1})^{*} R_{21}^{1} \\ = φ + 1.0 ɛ (1.0 ɛ)^{*} φ = φ \end{matrix}$ (37) $\begin{matrix} R_{22}^{2} = R_{22}^{1} + R_{22}^{1} (R_{22}^{1})^{*} R_{22}^{1} \\ = 1.0 ɛ + 1.0 ɛ (1.0 ɛ)^{*} 1.0 ɛ = 1.0 ɛ \end{matrix}$ (38) $\begin{matrix} R_{23}^{2} = R_{23}^{1} + R_{22}^{1} (R_{22}^{1})^{*} R_{23}^{1} \\ = φ + 1.0 ɛ (1.0 ɛ)^{*} φ = φ \end{matrix}$ (39) $R_{24}^{2} = R_{24}^{1} + R_{22}^{1} (R_{22}^{1})^{*} R_{24}^{1} = φ + φ = φ$ (40) $R_{3 j}^{2} = R_{3 j}^{1} + R_{33}^{1} (R_{33}^{1})^{*} R_{3 j}^{1}$ (41) $R_{3 j}^{2} = R_{3 j}^{1} + R_{33}^{1} (R_{33}^{1})^{*} R_{3 j}^{1} = R_{3 j}^{1} + ɛ R_{3 j}^{1}$ (42) $R_{31}^{2} = φ + φ = φ$ (43) $R_{32}^{2} = R_{32}^{1} + 1.0 ɛ R_{32}^{1} = φ$ (44) $R_{33}^{2} = R_{33}^{1} + 1.0 ɛ R_{33}^{1} = 1.0 ɛ$ (45) $R_{34}^{2} = R_{34}^{1} + 1.0 ɛ R_{34}^{1} = 1.0 y + 1.0 ɛ y = 1.0 y$ (46) $R_{ij}^{k} = R_{ij}^{(k - 1)} + R_{ik}^{(k - 1)} (R_{kk}^{(k - 1)})^{*} R_{kj}^{(k - 1)}$ (47) $R_{4 j}^{2} = R_{4 j}^{1} + R_{4 k}^{1} (R_{kk}^{1})^{*} R_{kj}^{1}$ (48) $R_{41}^{2} = R_{41}^{1} + R_{42}^{1} (R_{22}^{1})^{*} R_{21}^{1} = φ$ (49) $R_{42}^{2} = R_{42}^{1} + R_{42}^{1} (R_{22}^{1})^{*} R_{22}^{1} = φ$ (50) $R_{43}^{2} = R_{43}^{1} + R_{42}^{1} (R_{22}^{1})^{*} R_{23}^{1} = 1.0 x + φ = 1.0 x$ (51) $\begin{matrix} R_{44}^{2} = R_{44}^{1} + R_{42}^{1} (R_{22}^{1})^{*} R_{24}^{1} \\ = 1.0 ɛ + φ = 1.0 ɛ \end{matrix}$ (52) $R_{ij}^{k} = R_{ij}^{(k - 1)} + R_{ik}^{(k - 1)} (R_{kk}^{(k - 1)})^{*} R_{kj}^{(k - 1)}$ (53) $\begin{matrix} k = 3 \\ R_{1 j}^{3} = R_{1 j}^{2} + R_{13}^{2} (R_{33}^{2})^{*} R_{3 j}^{2} \end{matrix}$ (54) $R_{11}^{3} = R_{11}^{2} + R_{13}^{2} (ɛ)^{*} R_{31}^{2} = 1.0 ɛ + φ = 1.0 ɛ$ (55) $R_{12}^{3} = R_{12}^{2} + R_{13}^{2} (ɛ)^{*} R_{32}^{2} = 0.2 y$ (56) $\begin{matrix} R_{13}^{3} = R_{13}^{2} + R_{13}^{2} (ɛ)^{*} R_{33}^{2} \\ = 0.02 x + 0.02 x (1.0 ɛ)^{*} 1.0 ɛ = 0.02 x \end{matrix}$ (57) $\begin{matrix} R_{14}^{3} = R_{14}^{2} + R_{13}^{2} (ɛ)^{*} R_{34}^{2} \\ = φ + (0.02 x) 1.0 y = (0.02 x) y \end{matrix}$ (58) $R_{2 j}^{3} = R_{2 j}^{2} + R_{23}^{2} (R_{33}^{2})^{*} R_{3 j}^{2}$ (59) $R_{21}^{3} = R_{21}^{2} + R_{23}^{2} (R_{33}^{2})^{*} R_{21}^{2} = φ$ (60) $\begin{matrix} R_{22}^{3} = R_{22}^{2} + R_{23}^{2} (R_{33}^{2})^{*} R_{32}^{2} \\ = 1.0 ɛ + φ = 1.0 ɛ \end{matrix}$ (61) $R_{23}^{3} = R_{23}^{2} + R_{23}^{2} (R_{33}^{2})^{*} R_{33}^{2} = φ$ (62) $R_{24}^{3} = R_{24}^{2} + R_{23}^{2} (R_{33}^{2})^{*} R_{34}^{2} = φ$ (63) $R_{3 j}^{3} = R_{3 j}^{2} + R_{33}^{2} (R_{33}^{2})^{*} R_{3 j}^{2} = R_{3 j}^{2} + R_{3 j}^{2}$ (64) $R_{31}^{3} = φ R_{32}^{3} = φ R_{33}^{3} = ɛ R_{34}^{3} = 1.0 y$ (65) $R_{4 j}^{3} = R_{4 j}^{2} + R_{43}^{2} (R_{33}^{2})^{*} R_{3 j}^{2} = R_{4 j}^{2} + {xR}_{3 j}^{2}$ (66) $R_{41}^{3} = φ + 1.0 x φ = φ$ (67) $R_{42}^{3} = φ + 1.0 x φ = φ$ (68) $\begin{matrix} R_{43}^{3} = R_{43}^{2} + R_{43}^{2} (R_{33}^{2})^{*} R_{33}^{2} \\ = 1.0 x + 1.0 x = 1.0 x \end{matrix}$ (69) $\begin{matrix} R_{44}^{3} = 1.0 ɛ + 1.0 x 1.0 y = 1.0 ɛ + xy \\ k = 4 \end{matrix}$ (70) $R_{1 j}^{4} = R_{1 j}^{3} + R_{14}^{3} (R_{44}^{3})^{*} R_{4 j}^{3}$ (71) $R_{11}^{4} = ɛ + φ = 1.0 ɛ$ (72) $\begin{matrix} R_{12}^{4} = R_{12}^{3} + R_{14}^{3} (R_{44}^{3})^{*} R_{42}^{3} \\ = 0.2 y + (0.02 x) 1.0 y (1.0 ɛ + 1.0 x 1.0 y)^{*} φ \\ = 0.2 y \end{matrix}$ (73) $\begin{matrix} R_{13}^{4} = R_{13}^{3} + (0.02 x) 1.0 y (1.0 ɛ + 1.0 x 1.0 y)^{*} R_{43}^{3} \\ = 0.02 x + (0.02 x) 1.0 y (1.0 ɛ + 1.0 x 1.0 y)^{*} 1.0 x \\ = 0.02 x + (0.02 x) y (xy)^{*} x \\ = 0.02 x (1.0 ɛ + y (xy)^{*} x) = (0.02 x) (yx)^{*} \end{matrix}$ (74) $\begin{matrix} R_{14}^{4} = R_{14}^{3} + R_{14}^{3} (R_{44}^{3})^{*} R_{44}^{3} \\ = (0.02 x) 1.0 y + (0.02 x) 1.0 y \\ (1.0 ɛ + 1.0 x 1.0 y)^{*} (1.0 ɛ + 1.0 x 1.0 y) \end{matrix}$ (75) $R_{2 j}^{4} = R_{2 j}^{3} + R_{24}^{3} (R_{44}^{3})^{*} R_{4 j}^{3}$ (76) $R_{21}^{4} = R_{21}^{3} + φ = φ$ (77) $R_{22}^{4} = 1.0 ɛ$ (78) $R_{23}^{4} = φ$ (79) $R_{24}^{4} = φ$ (80) $\begin{matrix} R_{3 j}^{4} = R_{3 j}^{3} + R_{34}^{3} (R_{44}^{3})^{*} R_{4 j}^{3} = R_{3 j}^{3} + y (ɛ + xy)^{*} \\ R_{4 j}^{3} \end{matrix}$ (81) $R_{31}^{4} = φ + 1.0 y (1.0 ɛ + 1.0 xy)^{*} φ = φ$ (82) $R_{32}^{4} = φ + φ = φ$ (83) $\begin{matrix} R_{33}^{4} = 1.0 ɛ + 1.0 y (1.0 ɛ + 1.0 xy)^{*} x \\ = 1.0 ɛ + y (xy)^{*} x = (yx)^{*} \end{matrix}$ (84) $\begin{matrix} R_{34}^{4} = R_{34}^{3} + R_{34}^{3} (R_{44}^{3})^{*} R_{44}^{3} \\ = 1.0 y + 1.0 y (1.0 ɛ + 1.0 xy)^{*} (1.0 ɛ + 1.0 xy) \\ = 1.0 y (1.0 ɛ + (1.0 ɛ + 1.0 xy)^{*} (1.0 ɛ + 1.0 xy)) \\ = y (ɛ + xy)^{*} = y (xy)^{*} \end{matrix}$ (85) $\begin{matrix} R_{4 j}^{4} = R_{4 j}^{3} + R_{44}^{3} (R_{44}^{3})^{*} R_{4 j}^{3} \\ = R_{4 j}^{3} + (ɛ + xy) (xy)^{*} R_{4 j}^{3} \end{matrix}$ (86) $\begin{matrix} R_{41}^{4} = R_{41}^{3} + R_{44}^{3} (R_{44}^{3})^{*} R_{41}^{3} \\ = R_{4 j}^{3} + (1.0 ɛ + 1.0 xy) (1.0 xy)^{*} R_{4 j}^{3} = φ \end{matrix}$ (87) $R_{42}^{4} = R_{42}^{3} + R_{44}^{3} (R_{44}^{3})^{*} R_{42}^{3} = φ$ (88) $\begin{matrix} R_{43}^{4} = R_{43}^{3} + R_{44}^{3} (R_{44}^{3})^{*} R_{43}^{3} \\ = 1.0 x + (1.0 ɛ + 1.0 xy) (1.0 xy)^{*} 1.0 x \end{matrix}$ (89) $\begin{matrix} R_{44}^{4} = R_{44}^{3} + R_{44}^{3} (R_{44}^{3})^{*} R_{44}^{3} \\ = (1.0 ɛ + 1.0 xy) + (1.0 ɛ + 1.0 xy) \\ (1.0 xy)^{*} (1.0 ɛ + 1.0 xy) \end{matrix}$ (90)

Final states are {(P₁/0.2) , (P₃/1) , (P₄/1)}

$R_{11}^{4} = {ɛ}$ and final state is having membership 0.2. $Hence R_{11}^{4} = {1.0 \otimes 0.2 ɛ} = 0.2 ɛ$ (91)

$R_{12}^{4} = {0.2 y}$ and final state is having membership 1. $Hence R_{12}^{4} = {1.0 \otimes 0.2 y \otimes 1.0}$ (92) $\begin{matrix} R_{14}^{4} = 1.0 \otimes 1.0 \otimes (0.02 x) y \\ + (0.02 x) y (ɛ + xy)^{*} (ɛ + xy) \\ = (0.02 x) y + (0.02 x) y (ɛ + xy)^{*} (ɛ + xy) \\ = (0.02 x) y (ɛ + (ɛ + xy)^{*} (ɛ + xy)) \\ = (0.02 x) y (ɛ + (ɛ + xy)^{*} (ɛ + xy)) \\ = (0.02 x) y (ɛ + xy)^{+} = (0.02 x) y (xy)^{*} \end{matrix}$ (93)

Final regular expression equivalent to fuzzy automaton $\begin{matrix} = R_{11}^{4} + R_{12}^{4} + R_{14}^{4} = 0.2 + 0.2 y + (0.02 x) y (xy)^{*} \\ = 0.2 (ɛ + (0.1 x) y (xy)^{*}) + 0.2 y \\ = 0.2 ((0.1) (xy)^{*}) + 0.2 y = 0.2 ((0.1) (xy)^{*}) + y) \end{matrix}$ (94)

5 Concluding remarks and future work

From an experimental perspective, we have described an algorithm for the conversion of fuzzy automata into fuzzy regular expressions. This algorithm is founded on the concept of the transitive closure. Furthermore, we have proven that there exists a fuzzy regular expression r corresponding to the fuzzy automaton M such that L (r) = L (M). This method is computationally attractive, as demonstrated through the illustrative example. Fuzzy regular expressions are useful in the field of approximate patterns in text, in fuzzy string matching, and in the description of programming languages.

Several attempts have been made to achieve the conversion of fuzzy regular expressions into fuzzy automata; however, to the author’s best knowledge, no successful conversion of fuzzy automata into fuzzy regular expressions has been proposed thus far. In the future, we plan to convert fuzzy regular expressions into fuzzy automata using fewer states.

References

Hussain

and Shabbir

, Soft finite state machine, Journal of Intelligent and Fuzzy System (2015). DOI: 10.3233/IFS-151642.

Kumar

and Verma

A.K.

, A novel algorithm for the conversion of shuffle regular expressions into non-deterministic finite automata, Maejo International Journal of Science and Technology7(3) (2013), 396–407.

Stamenković

and Ćirić

, Construction of fuzzy automata from fuzzy regular expressions, Fuzzy Sets and Systems199 (2012), 1–27.

Cao and Ezawa Nondeterministic fuzzy automata, Information Sciences191 (2012), 86–97.

Neumann

, Converting deterministic finite automata to regular expressions, http://neumannhaus.com/christoph/papers/-03-16.DFA_to_RegEx.pdf, 2005.

and Ko

, Problem Solving in Automata, Languages, and Complexity, John Wiley & Sons, New York, NY, 2001.

Qiu

, Supervisory control of fuzzy discrete event systems: A formal approach, IEEE Transactions on Systems, Man and Cybernetics-Part B35(1) (2005), 72–88.

Qiu

and Wang

, A probabilistic model of computing with words, Journal of Computer and System Sciences70(2) (2005), 176–200.

Santos

E.S.

, Maxmin automata, Information and Control13 (1968), 363–377.

10.

Lin

and Ying

, Modeling and control of fuzzy discrete even systems, IEEE Transactions on Systems, Man and Cybernetics, Part B32(4) (2002), 408–415.

11.

Nejad

H.C.

, Azadbakht

, Adenihvand

, Mohammadi

and Mirzamohammad

, Fuzzy cellular learning automata for lesion detection in retina images, Journal of Intelligent and Fuzzy System27(5) (2014), 2297–2303.

12.

Wang

and Qiu

, Computing with words via Turing machines: A Formal Approach, IEEE Transactions on Fuzzy Systems11(6) (2003), 742–753.

13.

Brzozowski

J.A.

, Derivatives of regular expressions, Journal of the ACM11(4) (1964), 481–494.

14.

Hopcroft

J.E.

and Ullman

J.D.

, Introduction to Automata Theory, Languages and Computation, Addison-Wesley Publishing Company, Reading, MA, 1979.

15.

Mordeson

J.N.

and Malik

D.S.

, Fuzzy Automata and Languages: Theory and Applications, Chapman & Hall/ CRC, Boca Raton, London, 2002.

16.

Mendivil

J.R.G.D.

and Garitagoitia

J.R.

, A Comment on “Construction of fuzzy automata from fuzzy regular expressions”, Fuzzy Sets and Systems262 (2015), 102–110.

17.

Singh

, Conversion of deterministic finite automata to regular expression using bridge state, Thapar University, M.E. Thesis, 2011.

18.

Zadeh

L.A.

, Fuzzy languages and their relation to human and machine intelligence, Proceeding International Conference on Man and Computer, S Karger, Basel, 1971, pp. 130–165 .

19.

Zadeh

L.A.

, Fuzzy sets, Information Control8 (1965), 338–353.

20.

Ilie

and Yu

, Follow automata, Information and Computation186(1) (2003), 140–162.

21.

Droste

and Gastin

, Weighted automata and weighted logics, Theoretical Computer Science380 (2007), 69–86.

22.

Ying

M.S.

, A formal model of computing with words, IEEE Transactions on Fuzzy Systems10(5) (2002), 640–652.

23.

Kumar

, Conversion of fuzzy regular expressions to fuzzy automata using the Follow automata, M.E. Thesis, Thapar University, 2014.

24.

Kumar

and Kumar

, Metamorphosis of fuzzy regular expressions to fuzzy automata using the follow automata, arXiv preprint arXiv:411.2865, 2014.

25.

Chhabra

and Kumar

, Review Paper on Conversion of Deterministic Finite Automata to Regular Expressions, International Conference On Engineering Innovation and Technology, Nagpur, 2012, pp. 21–24.

26.

Stańczyk

, Decision rule length as a basis for evaluation of attribute relevance, Journal of Intelligent & Fuzzy Systems24(3) (2013), 429–445.

27.

Wee

W.G.

and Fu

K.S.

, A formulation of fuzzy automata and its application as a model of learning systems, IEEE Transactions on Systems Man and Cybernetics5(3) (1969), 215–223.

28.

, A categorical approach to lattice-valued fuzzy automata, Fuzzy Sets and Systems157 (2006), 855–864.

29.

, Finite automata theory with membership values in lattices, Information Sciences181(5) (2011), 1003–1017.

30.

and Pedrycz

, Fuzzy finite automata and fuzzy regular expressions with membership values in lattice-ordered monoids, Fuzzy Sets and System156(1) (2005), 68–92.