Soft finite state machine

Abstract

Concept of soft finite state machine is being introduced, which is based on soft set theory. Concepts of soft successor and soft immediate successor are introduced and some of their properties are studied. Notions of soft subsystem, soft submachine are given here. Finally direct product of soft machines is studied.

Keywords

Soft subsystem soft submachine strongly soft connected Weakly soft connected

1 Introduction

During recent years soft set theory has gained popularity among the researchers due to its applications in various areas. Number of publications related to soft sets has risen exponentially. Theory of soft sets is proposed by Molodtsov in [16]. Basic aim of this theory is to introduce a mathematical model with enough parameters to handle uncertainty. Prior to soft set theory, probability theory, fuzzy set theory, rough set theory and interval mathematics were common tools to discuss uncertainty. But unfortunately difficulties were attached with these theories, for details see [11, 16]. As mentioned above soft set theory has enough number of parameters, so it is free from difficulties associated with other theories. Soft set theory has been applied to various fields very successfully.

Finite state machines were first introduced by Kleen [10]. He found its application in computer circuit designing and other areas.

Concept of fuzzy automata was introduced by Wee in [22]. The theory of fuzzy automata has been developed by many researchers like, Adamek and Wechler [1], Arbib and Manes [5, 6], Brunner and Wechler [7], Mizumoto et al. [15], Peeva et al. [18], Peeva [19, 20] and Sentos and Wee [21]. Malik et al. [12 –14] used algebraic techniques to study the fuzzy finite state machine, and introduced the notion of submachine of a finite state machine, retrievable, separated and connected fuzzy finite state machines and discussed their basic properties.

Soft set theory is a generalization of fuzzy set theory see [2]. There is a very close relationship between fuzzy set theory and soft set theory [4]. In this paper study of soft finite machine is initiated, which is a generalization of fuzzy finite state machine. Study of soft finite state machines is interesting and worthwhile because there are results which hold for fuzzy finite state machine but do not hold for soft finite machine. For example in fuzzy finite state machines if p is successor of q and r is a successor of p, then r is a successor of q. In general this result holds no longer in soft finite machines.

Arrangement of this paper is as the following. In Section 2, some basic notions related to finite state machines and soft sets are given. Notion of soft finite machine is introduced in Section 3. In this section concept of soft successor and soft immediate successor is introduced and some of its properties are discussed. Section 4, is devoted for the study of sub-systems and soft sub-machines. Here soft strongly connected submachines and direct product of soft machines is studied.

2 Preliminaries

In this section we review some basic notions related to finite state machines and soft sets. These will be required in later sections.

Definition 1. A six tuple $M = (Q, X, Y, f, g, s)$ is called a finite state machine if Q, X, and Y are non-empty sets, f : Q × X → Q, g : Q × X ⟶ Y, and s ∈ Q .

The members of Q are called states. The members of X and Y are called input and output symbols respectively. The functions f and g are called the state transition and output functions, respectively. The state s is called the initial state.

A finite state automaton is a finite state machine such that the set of output symbols Y is {0, 1 } . Further algebraic properties can be found in [8].

Concept of fuzzy automata is given by Wee in [22]. Latter different approaches for the fuzzification of finite state machine presented in detail in [9, 17].

Now we recall the basic definitions of soft set. Throughout this paper U refers to an initial universe set, P (U) the power set of U and E the set of all possible parameters under consideration with respect to U.

Definition 2. [16] A pair (F, A) is called a soft set over U, where F is a mapping given by F : A ⟶ P (U) and A is a subset of E .

Definition 3. [3] Let (F, A) and (G, B) be two soft sets over a common universe U such that A ∩ B ≠ ∅ . The restricted intersection of (F, A) and (G, B) is denoted by (F, A) Cap (G, B) and is defined as (F, A) Cap (G, B) = (H, C) , where C = A ∩ B and for all e ∈ C, H (e) = F (e) ∩ G (e) .

Further algebraic operations on soft set can be found in [3].

3 Soft finite state machine

In this section concept of soft finite machines is being introduced. Here some related concept such as soft successor and soft immediate successor will be studied. Throughout this paper, all soft sets are considered over the same universal set U .

Definition 4. A soft finite state machine (SFSM) is a quadruple (Q, X, F, U) where Q and X are finite non-empty sets called the soft states and the set of soft input symbols, respectively, and (F, Q × X × Q) is a soft set over U .

Let X ^∗ denote the set of all words of element of X of finite length, λ denote the empty word in X ^∗ and denote the length of x for every x ∈ X ^∗ .

Definition 5. Let M = (Q, X, F, U) be a SFSM. Define soft set (F ^∗, Q × X ^∗ × Q) by $\begin{matrix} F^{*} (q, λ, p) & = & {\begin{matrix} U if q = p, \\ \emptyset otherwise . \end{matrix} \\ F^{*} (q, a, p) & = & F (q, a, p) \end{matrix}$ and $F^{*} (q, xa, p) = ⋃_{r \in Q} {F^{*} (q, x, r) \cap F (r, a, p)}$ for all x ∈ X ^∗, p, q ∈ Q and a ∈ X .

Example 1. Let Q ={ a, b } be the set of soft states and X ={ x, y } be the set of soft inputs. Consider the universal set U = { 1, 2, 3, 4 } . Then M = (Q, X, F, U) is described as

	a	b
(a,x)	∅	{1,3}
(a,y)	{1,2,3}	∅
(b,x)	{2,3}	{1,2}
(b,y)	∅	{2,4}

The above table can be read as, the image of (a, y, a) under F is {1, 2, 3 } . The image of (a, xy, a) under F ^∗ is ∅, Since F ^∗ (a, xy, a) =

⋃_r∈Q [F ^∗ (a, x, r) ∩ F (r, y, a)]

$= {\begin{matrix} [F^{*} (a, x, a) \cap F (a, y, a)] \cup \\ [F^{*} (a, x, b) \cap F (b, y, a)] \end{matrix}$

= [∅ ∩ { 1, 2, 3 }] ∪ [{ 1, 3 } ∩ ∅]

= ∅ .

Lemma 1. Let M = (Q, X, F, U) be a SFSM. Then F ^∗ (q, xy, p) = $⋃_{r \in Q} {F^{*} (q, x, r) \cap F^{*} (r, y, p)}$ for all p, q ∈ Q and x, y ∈ X ^∗ .

Proof. Let p, q ∈ Q and x, y ∈ X ^∗. We prove the result by induction on

if n = 0, then y = λ and so xy = xλ = x, hence

⋃_r∈Q [F ^∗ (q, x, r) ∩ F ^∗ (r, y, p)]

= ⋃ _r∈Q [F ^∗ (q, x, r) ∩ F ^∗ (r, λ, p)]

= F ^∗ (q, x, p) .

Thus the result is true for n = 0 .

Suppose that the result is valid for all u ∈ X ^∗ such that Let y = ua where u ∈ X ^∗, a ∈ X and Then F ^∗ (q, xy, p) = F ^∗ (q, xua, p) $\begin{matrix} = & ⋃_{r \in Q} [F^{*} (q, xu, r) \cap F (r, a, p)] \\ = & ⋃_{r \in Q} [\begin{matrix} ⋃_{s \in Q} [\begin{matrix} F^{*} (q, x, s) \cap \\ F^{*} (s, u, r) \end{matrix}] \\ \cap F (r, a, p) \end{matrix}] \\ = & ⋃_{r, s \in Q} [\begin{matrix} F^{*} (q, x, s) \cap F^{*} (s, u, r) \\ \cap F (r, a, p) \end{matrix}] \\ = & ⋃_{s \in Q} [\begin{matrix} F^{*} (q, x, s) \cap \\ {⋃_{r \in Q} [\begin{matrix} F^{*} (s, u, r) \cap \\ F (r, a, p) \end{matrix}]} \end{matrix}] \\ = & ⋃_{s \in Q} [F^{*} (q, x, s) \cap F^{*} (s, ua, p)] \\ = & ⋃_{s \in Q} [F^{*} (q, x, s) \cap F^{*} (s, y, p)] . \end{matrix}$

Hence the result is valid for This completes the proof.□

Definition 6. Let M = (Q, X, F, U) be a SFSM and let p, q ∈ Q . Then p is called a soft immediate successor of q if there exists a ∈ X such that F (q, a, p) ≠ ∅ . We denote by SIS (q) the set of all soft immediate successors of q .

We say that p is a soft successor of q if there exists x ∈ X ^∗ such that F ^∗ (q, x, p) ≠ ∅ . We denote by SS (q) the set of all soft successors of q . For any subset T of Q, the set of all soft successors of T denoted by SS (T) is defined to be the set $SS (T) = \cup {SS (q) : q \in T} .$

Proposition 1. Let M = (Q, X, F, U) be a SFSM. Then q ∈ SS (q) for every q ∈ Q .

Proof. It is obvious. Since $F^{*} (q, λ, q) = U$ so we have q ∈ SS (q) .□

Remark 1. Let M = (Q, X, F, U) be a SFSM. For any p, q, r ∈ Q .

SIS (p) ⊆ SS (p) for all p ∈ Q .

If p ∈ SS (q) and r ∈ SS (p), then r need not be in SS (q) . This is the interesting point which holds in fuzzy frame, but may not holds in soft frame. For this see the following example.

Example 2. Let Q ={ a, b, c } be the set of soft states and X ={ x, y, z } be the set of soft inputs. Consider the universal set U = { 1, 2, 3, 4 } . Then M = (Q, X, F, U) be described as

	a	b	c
(a,x)	{1,2}	∅	∅
(a,y)	∅	{1,3}	∅
(a,z)	∅	∅	∅
(b,x)	∅	∅
(b,y)	∅	{2,4}	∅
(b,z)	∅	∅	{4}
(c,x)	{2,3,4}	∅	∅
(c,y)	∅	∅	{1,3}
(c,z)	∅	{1}	∅

The above table can be read as, the image of (a, x, a) under F is {1, 2 } .

Obviously SIS (q) ⊆ SS (q) for all q ∈ QimpliesSIS (a) ⊆ SS (a) and clearly in the above table SIS (a)= { a, b } . We want to show that SIS (a) = SS (a) , it is enough to prove that c ∉ SS (a) . For this we show F ^∗ (a, w, c) =∅ for all w ∈ X ^∗ . Here we use mathematical induction on

If n = 0 . Then w = λ, hence

F ^∗ (a, w, c) = F ^∗ (a, λ, c) =∅. This result is true for n = 0 .

If n = 1 . Then w ∈ X, clearly

F ^∗ (a, w, c) =∅ for all w ∈ X . This result is also true for n = 1 .

Suppose that F ^∗ (a, w, c) =∅ for all w ∈ X ^∗ such that Let u = wt where w ∈ X ^∗, t ∈ X and Then F ^∗ (a, u, c) = F ^∗ (a, wt, c) $\begin{matrix} = & ⋃_{r \in Q} [F^{*} (a, w, r) \cap F (r, t, c)] \\ = & {\begin{matrix} [F^{*} (a, w, a) \cap F (a, t, c)] \cup \\ [F^{*} (a, w, b) \cap F (b, t, c)] \cup \\ [F^{*} (a, w, c) \cap F (c, t, c)] \end{matrix}} \end{matrix}$ Since t ∈ X, so if t = x or t = y we have F ^∗ (a, u, c) = ∅ . In particular if t = z, then we have F ^∗ (a, u, c) $\begin{matrix} = & F^{*} (a, w, b) \cap F (b, z, c) \\ = & F^{*} (a, w, b) \cap {4} . . . . . . . . . . . . (1) \end{matrix}$ It can easily be prove that 4 ∉ F ^∗ (a, w, b) for all w ∈ X ^∗ by using mathematical induction on Hence from (1) we have F ^∗ (a, u, c) =∅ for all u ∈ X ^∗ such that

Since F ^∗ (a, w, c) =∅ for all w ∈ X ^∗

impliesc ∉ SS (a) . Thus SS (a) = { a, b } . Similarly we can calculate SS (b) ={ a, b, c } and SS (c) = { a, b, c } .

Note that b ∈ SS (a) and c ∈ SS (b) but c ∉ SS (a) .

Proposition 2. Let M = (Q, X, F, U) be a SFSM. For any subsets A and B of Q, the following assertions hold.

If A ⊆ B, then SS (A) ⊆ SS (B) .

A ⊆ SS (A) .

SS (A) ⊆ SS (SS (A)) .

SS (A ∪ B) = SS (A) ∪ SS (B) .

SS (A ∩ B) ⊆ SS (A) ∩ SS (B) .

Proof. (i) Let q ∈ SS (A) = ∪ { SS (a) : a ∈ A } impliesq ∈ SS (a) for some a ∈ A . Then there exists x ∈ X ^∗ such that F ^∗ (a, x, q) ≠ ∅ .

Note that a ∈ A ⊆ Bimpliesq ∈ SS (B) . Thus SS (A) ⊆ SS (B) .

(ii) It is obvious.

(iii) Since A ⊆ SS (A) impliesSS (A) ⊆ SS (SS (A)) using (i) .

(iv) A ⊆ A ∪ B and B ⊆ A ∪ BimpliesSS (A) ⊆ SS(A ∪ B) and SS (B) ⊆ SS (A ∪ B) implies SS (A) ∪ SS (B)⊆SS (A ∪ B) .

Conversely,

let q∈ SS (A ∪ B) = ∪ { SS (z) : z ∈ A ∪ B }

impliesq ∈ SS (z) for some z ∈ A ∪ B . Then there exist some x ∈ X ^∗ such that F ^∗ (z, x, q)≠ ∅ $\begin{matrix} q \in SS (A) or q \in SS (B) \\ q \in SS (A) \cup SS (B) \end{matrix}$ Thus SS (A ∪ B) ⊆ SS (A) ∪ SS (B) . Hence SS (A ∪ B)= SS (A) ∪ SS (B) .

(v) Since A ∩ B ⊆ A and A ∩ B ⊆ BimpliesSS (A ∩ B) ⊆ SS (A) and SS (A ∩ B) ⊆ SS (B) impliesSS (A ∩ B) ⊆SS (A) ∩ SS (B) .□

Note that equality in (v) may not be hold in general. For this, in example 2, let A ={ a, b } and B = { a, c } . Then A ∩ B = { a } .

Clearly SS (A ∩ B) ≠ SS (A) ∩ SS (B) . Because SS (A ∩ B) = { a, b } , SS (A) ={ a, b, c } and SS (B) = { a, b, c } .

Definition 7. Let M = (Q, X, F, U) be a SFSM. We say that M satisfies the soft exchange property if for all p, q ∈ Q and T ⊆ Q, whenever $\begin{matrix} p \in SS (T \cup {q}) and p \notin SS (T) then q \in SS (T \cup {q}) . \end{matrix}$ Theorem 1. Let M = (Q, X, F, U) be a SFSM. Then the following assertions are equivalent.

M satisfies the soft exchange property.

(∀ p, q ∈ Q) p ∈ SS (q) ⇔ q ∈ SS (p) .

Proof. Assume that M satisfies the soft exchange property.

Let p, q ∈ Q be such that p ∈ SS (q) = SS (∅ ∪ { q }) .Note that p ∉ SS (∅) and so q ∈ SS (∅ ∪ { p }) = SS (p) .

Similarly if q ∈ SS (p) then p ∈ SS (q) .

Conversely suppose that (ii) is valid.

Let p, q ∈ Q and T ⊆ Q .

If p ∈ SS (T ∪ { q }) and p ∉ SS (T) , then p ∈ SS (q) .It follows from (ii) that q ∈ SS (p) ⊆ SS (T ∪ { p }) . Hence M satisfies the soft exchange property.□

4 Soft sub-systems and soft sub-machines

Study of subsystems and submachines is very important area. In this section concept of soft subsystems and soft submachines is being introduced. Direct product of two soft finite state machines is also studied here.

Therefore we begin with the following;

Definition 8. Let M = (Q, X, F, U) be a SFSM. Let $(\tilde{F}, Q)$ be a soft set. Then $(Q, \tilde{F}, X, F, U)$ is called a soft subsystem of M if

$\tilde{F} (p) \cap F (p, a, q) \subseteq \tilde{F} (q)$ for all p, q ∈ Q and a ∈ X .

If $(Q, \tilde{F}, X, F, U)$ is a soft subsystem of M, then we simply write $\tilde{M}$ for $(Q, \tilde{F}, X, F, U) .$

Example 3. Consider a SFSM M = (Q, X, F, U) as described in example 2. Let $(\tilde{F}, Q)$ be a soft set over U, defined as

$\tilde{F} (a) = {1, 4},$ $\tilde{F} (b) = {1, 2, 4}$

and $\tilde{F} (c) = {1, 4} .$

Then Clearly $\tilde{M}$ is a soft subsystem of M .

Theorem 2. Let M = (Q, X, F, U) be a SFSM and $(\tilde{F}, Q)$ be a soft set over U . Then $\tilde{M}$ is a soft subsystem of M if and only if $F^{*} (p, x, q) \cap \tilde{F} (p) \subseteq \tilde{F} (q) \forall p, q \in Q and x \in X^{*} .$

Proof. Suppose that $\tilde{M}$ is a soft subsystem of M . Let p, q ∈ Q and x ∈ X ^∗ . The proof is by induction on

If n = 0, then x = λ . Now if p = q, then $F^{*} (q, λ, q) \cap \tilde{F} (q) = \tilde{F} (q)$ If q ≠ p, then $F^{*} (p, λ, q) \cap \tilde{F} (p) = \emptyset \subseteq \tilde{F} (q)$ Thus the result is true for n = 0 .

Suppose that result is valid for all y ∈ X ^∗ with n > 0

Let x = ya where a ∈ X, then $\tilde{F} (p) \cap F^{*} (p, x, q)$ $\begin{matrix} = & \tilde{F} (p) \cap F^{*} (p, ya, q) \\ = & \tilde{F} (p) \cap [⋃_{r \in Q} {F^{*} (p, y, r) \cap F (r, a, q)}] \\ = & ⋃_{r \in Q} [\tilde{F} (p) \cap F^{*} (p, y, r) \cap F (r, a, q)] \\ \subseteq & ⋃_{r \in Q} [\tilde{F} (r) \cap F (r, a, q)] \\ \subseteq & \tilde{F} (q) \end{matrix}$

$\tilde{F} (p) \cap F^{*} (p, x, q) \subseteq \tilde{F} (q)$

Converse is trivial.□

Definition 9. Let M = (Q, X, F, U) be a SFSM and T ⊆ Q . Let (f, T × X × T) be a soft set and let ℑ = (T, X, f, U) be a SFSM. Then ℑ is called a soft submachine of M if

F ∣ _T×X×T = f,

SS (T) ⊆ T .

We assume that φ = (∅ , X, f, U) is a soft submachine of M . Obviously, if ℑ′ is a soft submachine of ℑ, and ℑ is soft submachine of M, then ℑ′ is a soft submachine of M . A soft submachine ℑ = (T, X, f, U) of a SFSM M = (Q, X, F, U) is said to be proper if T≠ ∅ and T ≠ Q .

Definition 10. A SFSM M = (Q, X, F, U) is said to be strongly soft connected if p ∈ SS (q) and weakly soft connected if p ∈ SS (SS (q)) for every p, q ∈ Q .

Every strongly soft connected SFSM M = (Q, X, F, U) is weakly soft connected, but converse may not be true in general.

Example 4. Consider the SFSM, which is described in example 2. Clearly SFSM is weakly soft connected but not strongly soft connected, because c∉SS (a) .

Theorem 3. Let M = (Q, X, F, U) be a SFSM and let ℑ_i = (T _i, X, F _i, U) i ∈ I be a family of soft submachines of M . Then we have

⋂_i∈I ℑ _i = (∩ _i∈I T _i, X, _Capi ∈I F _i, U) is a soft submachine of M .

⋃_i∈I ℑ _i = (∪ _i∈I T _i, X, F′, U) is a soft submachine of M

where F′ = F ∣ _{∪_i∈IT×X×∪_i∈IT}

Proof. Let (q, x, p) ∈ ∩ _i∈I T _i × X × ∩ _i∈I T _i . Then (_Capi ∈I F _i) (q, x, p) $\begin{matrix} = & ⋒_{i \in I} F_{i} (q, x, p) = ⋒_{i \in I} F (q, x, p) \\ = & F (q, x, p) \end{matrix}$ Hence F ∣ _{∩_i∈IT_i×X×∩_i∈IT_i} = _Capi ∈I F _i

Now $SS (\cap_{i \in I} T_{i}) \subseteq \cap_{i \in I} SS (T_{i}) \subseteq \cap_{i \in I} T_{i}$ Hence ⋂_i∈I ℑ _i is a soft submachine of M .

(ii) Since $\begin{matrix} SS (\cup_{i \in I} T_{i}) & = & \cup_{i \in I} SS (T_{i}) \\ \subseteq & \cup_{i \in I} T_{i} \end{matrix}$ Hence ⋃_i∈I ℑ _i is a soft submachine of M .□

Theorem 4. A SFSM M = (Q, X, F, U) is strongly soft connected if and only if M has no proper soft submachine.

Proof. Suppose that M = (Q, X, F, U) is strongly soft connected.

Let ℑ = (T, X, F′, U) be a soft submachine of M such that T ≠ ∅ . Then there exists q ∈ T, if p ∈ Q, then p ∈ SS (q) , since M is strongly soft connected. It follows that p ∈ SS (q) ⊆ SS (T) so that T = Q . Hence M = ℑ . i . e M has no proper soft submachine.

Conversely M has no proper soft submachines. Let p, q ∈ Q and let ℑ = (SS (q) , X, F′, U) where F′ = F ∣ _{SS(q)×X×SS(q)} . Then ℑ is a soft submachine of M and SS (q)≠ ∅ and so SS (q) = Q .

Thus p ∈ SS (q) , and therefore M is strongly soft connected.□

Definition 11. Let M _i = (Q _i, X _i, F _i, U) be SFSM, i = 1, 2 . Let η be a function of Q ₂ onto Q ₁ and let ζ be a function of X ₁ into X ₂ . Extended ζ to a function ζ ^∗ of $X_{1}^{*}$ into $X_{2}^{*}$ by

ζ ^∗ (x) = ζ (x ₁) ζ (x ₂) ζ (x ₃) . . . . ζ (x _n) where x = x ₁ x ₂ x ₃ . . . x _n and x _i ∈ X, i = 1, 2, . . . , n and ζ ^∗ (λ) = λ. Then (η, ζ) is called a covering of M ₁ by M ₂, written M ₁ ≤ M ₂, if and only if ∀q ₂ ∈ Q ₂, q ₁ ∈ Q ₁ and $x \in X_{1}^{*},$

$F_{1}^{*} (η (q_{2}), x, q_{1}) =$

$⋃ {F_{2}^{*} (q_{2}, ζ^{*} (x), r_{2}) ∣ η (r_{2}) = q_{1}, r_{2} \in Q_{2}} .$

Let M _i = (Q _i, X _i, F _i, U) be SFSM, i = 1, 2 . Let $\bar{X}$ be a finite set and f a function from $\bar{X}$ into X ₁ × X ₂ . Let π _i be the projection map of X ₁ × X ₂ onto X _i, i = 1, 2 .

Let $(F_{f}, (Q_{1} \times Q_{2}) \times \bar{X} \times (Q_{1} \times Q_{2}))$ be a soft set over U defined as follows: ∀ (q ₁, q ₂) , (p ₁, p ₂) ∈ Q ₁ × Q ₂ and $a \in \bar{X},$

F _f ((q ₁, q ₂) , a, (p ₁, p ₂)) =

F ₁ × F ₂ ((q ₁, q ₂) , (π ₁ (f (a)) , π ₂ (f (a))) , (p ₁, p ₂)) .

Then $(Q_{1} \times Q_{2}, \bar{X}, F_{f}, U)$ is called the general direct product of M ₁ and M ₂ and we write M ₁ ∗ M ₂ for $(Q_{1} \times Q_{2}, \bar{X}, F_{f}, U) .$

Note that

F ₁ × F ₂ ((q ₁, q ₂) , (a ₁, a ₂) , (p ₁, p ₂)) =

F ₁ (q ₁, a ₁, p ₁) ∩ F ₂ (q ₂, a ₂, p ₂)

∀ (q ₁, q ₂) , (p ₁, p ₂) ∈ Q ₁ × Q ₂ and ∀ (a ₁, a ₂) ∈ X ₁ × X ₂ .

If $\bar{X} = X_{1} \times X_{2}$ and f is the identity map, then M ₁ ∗ M ₂ is called the full direct product of M ₁ and M ₂ and we write M ₁ × M ₂ .

If X ₁ = X ₂,

$\bar{X} = {\begin{matrix} (a_{1}, a_{2}) ∣ a_{i} \in X_{i}, \\ i = 1, 2, a_{1} = a_{2} \end{matrix}}$ and f is the identity map, then M ₁ ∗ M ₂ is called the restricted direct product of M ₁ and M ₂ and we write M ₁ × _R M ₂ forM ₁ ∗ M ₂ .

Lemma 2. Let M _i = (Q _i, X _i, F _i, U) be a SFSM, i = 1, 2 . Consider the general direct product M ₁ ∗ M ₂ . Then

$F_{f}^{*} ((q_{1}, q_{2}), λ, (p_{1}, p_{2})) = F_{1}^{*} (q_{1}, λ, p_{1}) \cap F_{2}^{*} (q_{2}, λ, p_{2}) \forall q_{1}, p_{1} \in Q_{1}, q_{2}, p_{2} \in Q_{2} .$

$F_{f}^{*} ((q_{1}, q_{2}), \bar{a_{1}} . . . \bar{a_{n}}, (p_{1}, p_{2})) =$

${\begin{matrix} F_{1}^{*} (q_{1}, π_{1} (f (\bar{a_{1}})) . . . π_{1} (f (\bar{a_{n}})), p_{1}) \cap \\ F_{2}^{*} (q_{2}, π_{2} (f (\bar{a_{1}})) . . . π_{2} (f (\bar{a_{n}})), p_{2}) \end{matrix}$

where

\bar{a_{i}} \in \bar{X}, i = 1, 2, . . . n, \forall q_{1}, p_{1} \in Q_{1}, q_{2}, p_{2} \in Q_{2} .

Proof. (i) The proof is straightforward.

(ii) $F_{f}^{*} ((q_{1}, q_{2}), \bar{a_{1}} . . . \bar{a_{n}}, (p_{1}, p_{2}))$

$= ⋃_{(r_{1}^{(i)}, r_{2}^{(i)}) \in Q_{1} \times Q_{2} i = 1, 2, . . . n - 1}$

${\begin{matrix} F_{f} ((q_{1}, q_{2}), \bar{a_{1}}, (r_{1}^{(1)}, r_{2}^{(1)})) \cap \\ F_{f} ((r_{1}^{(1)}, r_{2}^{(1)}), \bar{a_{2}}, (r_{1}^{(2)}, r_{2}^{(2)})) \cap . . . . \\ \cap F_{f} ((r_{1}^{(n - 1)}, r_{2}^{(n - 1)}), \bar{a_{n}}, (p_{1}, p_{2})) \end{matrix}}$

$= ⋃_{(r_{1}^{(i)}, r_{2}^{(i)}) \in Q_{1} \times Q_{2} i = 1, 2, . . . n - 1}$

${\begin{matrix} F_{1} \times F_{2} (\begin{matrix} (q_{1}, q_{2}), \\ (\begin{matrix} π_{1} (f (\bar{a_{1}})), \\ π_{2} (f (\bar{a_{1}})) \end{matrix}), \\ (r_{1}^{(1)}, r_{2}^{(1)}) \end{matrix}) \cap \\ F_{1} \times F_{2} (\begin{matrix} (r_{1}^{(1)}, r_{2}^{(1)}), \\ (\begin{matrix} π_{1} (f (\bar{a_{2}})), \\ π_{2} (f (\bar{a_{2}})) \end{matrix}), \\ (r_{1}^{(2)}, r_{2}^{(2)}) \end{matrix}) \cap . . . \\ \cap F_{1} \times F_{2} (\begin{matrix} (r_{1}^{(n - 1)}, r_{2}^{(n - 1)}), \\ (\begin{matrix} π_{1} (f (\bar{a_{n}})), \\ π_{2} (f (\bar{a_{n}})) \end{matrix}), \\ (p_{1}, p_{2}) \end{matrix}) \end{matrix}}$

$= ⋃_{r_{1}^{(i)} \in Q_{1}, r_{2}^{(i)} \in Q_{2} i = 1, 2, . . . n - 1}$

${\begin{matrix} F_{1} (q_{1}, π_{1} (f (\bar{a_{1}})), r_{1}^{(1)}) \cap \\ F_{2} (q_{2}, π_{2} (f (\bar{a_{1}})), r_{2}^{(1)}) \cap \\ F_{1} (r_{1}^{(1)}, π_{1} (f (\bar{a_{2}})), r_{1}^{(2)}) \cap \\ F_{2} (r_{2}^{(1)}, π_{2} (f (\bar{a_{2}})), r_{2}^{(2)}) \cap . . . . \cap \\ F_{1} (r_{1}^{(n - 1)}, π_{1} (f (\bar{a_{n}})), p_{1}) \cap \\ F_{2} (r_{2}^{(n - 1)}, π_{2} (f (\bar{a_{n}})), p_{2}) \end{matrix}}$

$= {\begin{matrix} {⋃_{r_{1}^{(i)} \in Q_{1} i = 1, 2, . . . n - 1} {\begin{matrix} F_{1} (\begin{matrix} q_{1}, \\ π_{1} (f (\bar{a_{1}})), \\ r_{1}^{(1)} \end{matrix}) \cap \\ F_{1} (\begin{matrix} r_{1}^{(1)}, \\ π_{1} (f (\bar{a_{2}})), \\ r_{1}^{(2)} \end{matrix}) \cap . . . . \cap \\ F_{1} (\begin{matrix} r_{1}^{(n - 1)}, \\ π_{1} (f (\bar{a_{n}})), \\ p_{1} \end{matrix}) \end{matrix}}} ⋂ \\ {⋃_{r_{2}^{(i)} \in Q_{2} i = 1, 2, . . . n - 1} {\begin{matrix} F_{2} (\begin{matrix} q_{2}, \\ π_{2} (f (\bar{a_{1}})), \\ r_{2}^{(1)} \end{matrix}) \cap \\ F_{2} (\begin{matrix} r_{2}^{(1)}, \\ π_{2} (f (\bar{a_{2}})), \\ r_{2}^{(2)} \end{matrix}) \cap . . . . \cap \\ F_{2} (\begin{matrix} r_{2}^{(n - 1)}, \\ π_{2} (f (\bar{a_{n}})), \\ p_{2} \end{matrix}) \end{matrix}}} \end{matrix}$ $= {\begin{matrix} F_{1}^{*} (q_{1}, π_{1} (f (\bar{a_{1}})) . . . π_{1} (f (\bar{a_{n}})), p_{1}) \cap \\ F_{2}^{*} (q_{2}, π_{2} (f (\bar{a_{1}})) . . . π_{2} (f (\bar{a_{n}})), p_{2}) . \end{matrix}$ □

Corollary 1. Let M _i = (Q _i, X _i, F _i, U) be a SFSM,i = 1, 2 . Then

${(F_{1} \times F_{2})}^{*} = F_{1}^{*} \times F_{2}^{*}$

${(F_{1} \times_{R} F_{2})}^{*} = F_{1}^{*} \times_{R} F_{2}^{*}$

5 Conclusion

In this paper concept of soft finite state machine, soft subsystem, soft submachine and products of soft finite state machine is introduced. A necessary and sufficient condition for a soft subsystem is obtained. We hope the research can be continued along this direction. In future, cyclic soft subsystem, simple strong soft subsystem and the algebraic properties of the products of soft finite state machine can be studied.

References

10.

11.

12.

13.

14.

15.

16.

17.

18.

19.

20.

21.

22.