# Semitensor Product Approach to Controllability, Reachability, and Stabilizability of Probabilistic Finite Automata

Authors: Wenhui Dou; Haitao Li; Fuad E. Alsaadi
Journal: Mathematical Problems in Engineering
 (2019)

---

## Abstract

This paper proposes a matrix-based approach to investigate the controllability, reachability, and stabilizability of probabilistic finite automata (PFA). Firstly, the state transition probabilistic structure matrix is constructed for PFA, based on which a kind of controllability matrix is defined for PFA. Secondly, some necessary and sufficient conditions are presented for the controllability, reachability, and stabilizability of PFA with positive probability by using the controllability matrix. Finally, an illustrate example is given to validate the obtained new results.


---

## Body

## 1. Introduction

Finite automaton is a kind of finite-state machine which plays a key role in theoretical computer science. There are many kinds of finite automata, such as deterministic finite automata (DFA) [1, 2], nondeterministic finite automata (NFA) [3], probabilistic finite automata (PFA) [4, 5], and so on. In the past few decades, finite automata has attracted lots of scholars’ research interest in many disciplines such as computer science, applied mathematics, and engineering, and some fundamental results have been presented [6, 7].Especially, finite automaton is an important model of discrete event systems (DESs). Another effective model of DESs is Petri net. As we all know, controllability, reachability, and observability are fundamental concepts in DESs [8–10]. The concepts of controllability and observability are extensively studied in Petri nets [11–14], while the concept of reachability is intrinsic to both finite automata [1, 2] and Petri nets [15]. In finite automata, the concept of reachability comes from the classic control theory, which depends on the occurrence events of every state [1, 2]. However, in bounded Petri nets, the concept of reachability depends on transitions and tokens of every marking, which is quite different from that of finite automata [15].Recently, PFA has been extensively studied because it generalizes the concept of NFA by adding transition probability to the transition function and has wider applications [16–18]. The state estimation and detectability of PFA were considered in [4, 19], and some necessary and sufficient conditions were presented. The supervisory control of PFA was investigated in [20], and several supervisor synthesis problems were proposed.In some recent works, a semitensor product (STP) approach [21] has been introduced to the reachability and stabilizability of finite automata [1, 2, 22]. For other applications of STP in Boolean networks [23–25] and game theory [26–28], please refer to [29–35]. Xu et al. [1] developed an STP-based method for the reachability of DFA. Yan et al. [2] presented some new criteria for the controllability, reachability and stabilizability of DFA by using STP. Zhang et al. [18] established the algebraic form of PFA via STP and studied the reachability of PFA with positive probability and with probability one, respectively. However, to our best knowledge, there are fewer results on the analysis of controllability and stabilizability of PFA.In this paper, we propose a matrix-based approach to investigate the controllability, reachability, and stabilizability of PFA with positive probability. The main contributions of this paper are twofold. On one hand, we construct the controllability matrix for PFA, which is effective for the analysis of PFA. On the other hand, some necessary and sufficient conditions are obtained for the controllability, reachability, and stabilizability of PFA with positive probability. These conditions are based on the controllability matrix, and easily verified via MATLAB. Compared with the existing results [18], this paper introduces the concept of controllability and stabilizability for PFA with positive probability.The rest of this paper is organized as follows. Section2 introduces some necessary preliminaries on PFA. Section 3 presents some necessary and sufficient conditions for the controllability, reachability, and stabilizability of PFA with positive probability. In Section 4, an example is given to illustrate the new results, which is followed by a brief conclusion in Section 5.Notations. M i , j is the (i,j)-th element of matrix M. 0n=[00⋯0︸n]∈R1×n. δni represents the i-th column of the identity matrix In. Δn≔{δn1,⋯,δnn}. The matrix product of this paper is the semitensor product of matrices [21]. We often omit the symbol “⋉” if no confusion arises.


## 2. Preliminaries on PFA

A probabilistic finite automata is a five-tupleΛ=(X,Σ,f,x0,p), where X={x1,x2,⋯,xn} is the finite set of states, x0∈X is the initial state, Σ={σ1,⋯,σm} is the finite set of events called alphabet, Σ∗ is the finite input string set on Σ, and f:X×Σ→2X is the partial transition function. Given a state xp∈X and a finite input string s=σ(0)σ(1)⋯σ(t-1)∈Σ∗, we define f(xp,s)=f(⋯f(f(xp,σ(0)),σ(1)),⋯,σ(t-1)). In this paper, we assume that, for any state x∈X, there exists an event σ∈Σ such that f(x,σ)∈X. p:X×Σ×X→[0,1] is the state transition probabilistic function, that is, p(xp,σ,xq) means the probability from state xp to state xq with the occurrence of event σ. We notice that ∑σ∈Σ∑xq∈Xp(xp,σ,xq)=1 holds for any xp∈X.Now, we present the concepts of controllability, reachability, and stabilizability for PFA.Definition 1.
( 1 ) The state xα∈X is said to be controllable to the state xβ∈X with positive probability, if there exists a finite input sequence s∈Σ∗, s≥1, such that p(xα,s,xβ)>0. Here, s means the length of finite input sequence s.
( 2 ) The state xα∈X is said to be controllable with positive probability, if the state xα∈X is controllable to any state xβ∈X with positive probability.Definition 2.
( 1 ) The state xβ∈X is said to be reachable from the state xα∈X with positive probability, if there exists a finite input sequence s∈Σ∗, s≥1, such that p(xα,s,xβ)>0.
( 2 ) The state xβ∈X is said to be reachable with positive probability, if the state xβ∈X is reachable from any state xα∈X with positive probability.Given two nonempty setsX1⊆X and X2⊆X, we assume that(1)X1∪X2=X,X1∩X2=∅. Then, we give the concepts of controllability, reachability and stabilizability of nonempty sets of states.Definition 3.
The nonempty set of statesX1⊆X is said to be controllable with positive probability, if for any state xβ∈X2, there exists a state xα∈X1 such that xα is controllable to xβ with positive probability.Definition 4.
The nonempty set of statesX2⊆X is said to be reachable with positive probability, if for any state xα∈X1, there exists a state xβ∈X2 such that xβ is reachable from xα with positive probability.Definition 5.
The nonempty set of statesX1⊆X is said to be one-step returnable with positive probability, if for any state xα∈X1, there exist an event σ∈Σ and a state xβ∈X1 such that p(xα,σ,xβ)>0.Definition 6.
The nonempty set of statesX1⊆X is said to be stabilizable with positive probability, if X1 is reachable with positive probability and one-step returnable with positive probability.Example 7.
Consider a PFAΛ=(X,Σ,f,x0,p), where X={x1,x2,x3,x4}, Σ={a,b}, x0=x1, and f and p are shown in Figure 1.Figure 1
A probabilistic finite automata.From Figure1, we can see that x1→b/0.2x2→b/0.5x4→b/0.5x3→b/0.5x1. Therefore, by Definitions 1 and 2, x1, x2, x3, and x4 are controllable and reachable with positive probability.Assume thatX1={x1,x2} and X2={x3,x4}. Since x1∈X1→b/0.2x2→b/0.5x4∈X2 and x1∈X1→a/0.4x3∈X2, by Definition 3, X1 is controllable with positive probability. Similarly, X2 is also controllable with positive probability. Since x3→a/0.5x4→b/0.5x1→b/0.2x2 and x1→b/0.2x2→b/0.5x4→b/0.5x3, by Definition 4, we can obtain that X1 and X2 are reachable with positive probability. Since x3→a/0.5x4 and x4→b/0.5x3, by Definition 5, X2 is one-step returnable with positive probability. Hence, by Definition 6, X2 is stabilizable with positive probability.


## 3. Main Results

In this section, we give a controllability matrix to investigate the probability finite automata (PFA) about its controllability, reachability, and stabilizability.Given a PFAΛ=(X,Σ,f,x0,p), we identify xα~δnα, α=1,⋯,n, σt~δmt, t=1,⋯,m, and (Pt)β,α≔p(xα,σt,xβ).We construct the state transition probabilistic structure matrix (STPSM) ofΛ as (2)L=L1⋯Lm∈Rn×mn, where Lt∈Rn×n is defined as follows: (3)Ltβ,α≔Ptβ,α,ifδnβ∈fδnα,δmt,0,otherwise.Based on the construction ofL, the considered PFA has the following algebraic form: (4)Ext+1=LutExt, where Ex(t) is the mathematic expectation of states at time t, u(t)∈Δm is the vector of events at time t, and L is the STPSM.For any positive integert, let(5)K≔11⋯1111⋯12⋮⋮⋮⋮⋮11⋯1m11⋯21⋮⋮⋮⋮⋮mm⋯mm-1mm⋯mm︷t∈Rmt×t.Then, the i-th row of matrix K, denoted by (Ki,1,⋯,Ki,t), represents the choice of {LKi,1,⋯,LKi,t} in {L1L2⋯Lm}.Define(6)Mt=H1t,H2t,⋯,Hmtt, where Hi(t)=∏j=1tLKi,t-j+1. Then, M(t) denotes the set of t-step transition probability matrices associated with all possible inputs with length t.Given a finite input sequences=σ(0)σ(1)⋯σ(t-1)∈Σ∗ with s~δmtr, by (4) and (6), we have (7)Ext=Lσt-1Ext-1=LKr,tLσt-2Ext-2=LKr,tLKr,t-1Lσt-3Ext-3=⋯=LKr,tLKr,t-1⋯σ0x0=LKr,tLKr,t-1⋯LKr,1x0=Hrtx0.Set(8)Mt=∑i=1mtHit∈Rn×n. Comparing (6) with (∑i=1mLi)t, one can find that (9)Mt=∑i=1mLit∈Rn×n.Theorem 8.
(1) The statexα is controllable to the state xβ with positive probability, if and only if there exists a positive integer τ such that (C)β,α>0, where (10)C=∑t=1τMt.
(2) The statexα is controllable with positive probability, if and only if there exists a positive integer τ such that (11)ColαC=Colα∑t=1τMt>0n⊤.Proof.
We firstly prove conclusion (1).
(Necessity) Suppose that the statexα is controllable to the state xβ with positive probability. By Definition 1, there exists a finite input sequence s=σ(0)σ(1)⋯σ(τ-1)∈Σ∗ such that p(xα,s,xβ)>0. We assume that s~δmτr. By (7), one can see that (Hr(τ))β,α>0, which shows that (12)Mτβ,α=∑i=1mτHiτβ,α≥Hrτβ,α>0. Therefore, there exists a positive integer τ such that (C)β,α=∑t=1τ(Mt)β,α≥(Mτ)β,α>0 holds.
(Sufficiency) Suppose that there exists a positive integerτ such that (C)β,α=∑t=1τ(Mt)β,α>0. Then, there exists a positive integer λ≤τ such that (Mλ)β,α>0. Since (Mλ)β,α=∑i=1mλ(Hi(λ))β,α>0, there exists a positive integer r≤mλ such that (Hr(λ))β,α>0. By (7), one can find a finite input sequence s=σ(0)σ(1)⋯σ(λ-1)∈Σ∗ with s~δmλr, such that p(xα,s,xβ)=(Hr(λ))β,α>0. By Definition 1, xα is controllable to xβ with positive probability.
In the following, we prove conclusion(2).
(Necessity) Suppose that the statexα~δnα is controllable with positive probability. By Definition 1, for any state xβ~δnβ, δnα is controllable to δnβ with positive probability. Then, by conclusion (1) of Theorem 8, there exists a positive integer τβ such that (13)∑t=1τβMtβ,α>0.Let τ=max⁡{τβ:β=1,2,⋯,n}. Then, one can obtain that (14)Colα∑t=1τMt>0n⊤.
(Sufficiency) Suppose that there exists a positive integerτ such that (11) holds. Then for any β=1,⋯,n, we have ∑t=1τ(Mt)β,α>0. By conclusion (1) of Theorem 8, the state xα is controllable to the state xβ with positive probability. Since β is arbitrary, the state xα∈X is controllable to any state xβ∈X with positive probability. By Definition 1, the state xα∈X is controllable with positive probability.Theorem 9.
(1) The statexβ is reachable from the state xα with positive probability, if and only if there exists a positive integer τ such that (C)β,α>0.
(2) The statexβ is reachable with positive probability, if and only if there exists a positive integer τ such that (15)RowβC=Rowβ∑t=1τMt>0n.Proof.
The proof of conclusion (1) is very similar to that of Theorem8. We just prove conclusion (2).
(Necessity) Suppose that the statexβ~δnβ is reachable with positive probability. By Definition 2, for any state xα~δnα, δnβ is reachable from δnα with positive probability. From conclusion (1) of Theorem 9, there exists a positive integer τα such that (16)∑t=1ταMtβ,α>0. Set τ=max{τα:α=1,2,⋯,n}. It is easy to see that (15) holds.
(Sufficiency) Suppose that there exists a positive integerτ such that (15) holds. Then for any α=1,⋯,n, we have ∑t=1τ(Mt)β,α>0. By conclusion (1) of Theorem 9, the state xβ is reachable from the state xα with positive probability. Since α is arbitrary, one can obtain that the state xβ∈X is reachable from any state xα∈X with positive probability. By Definition 2, the state xβ∈X is reachable with positive probability.Given the two nonempty sets of states(17)X1=δnα1,δnα2,⋯,δnαl,X2=δnαl+1,δnαl+2,⋯,δnαn, it is obvious that X1∪X2=X and X1∩X2=∅.According to (9) and (10), we define the following matrices: (18)CX1=∑j=1lCαl+1,αj∑j=1lCαl+2,αj⋯∑j=1lCαn,αj,(19)RX2=∑i=l+1nCαi,α1∑i=l+1nCαi,α2⋯∑i=l+1nCαi,αl,(20)MX1=∑i=1lMαi,α1∑i=1lMαi,α2⋯∑i=1lMαi,αl.Theorem 10.
X 1 ⊆ X is controllable with positive probability, if and only if CX1>0n-l.Proof.
(Necessity) Suppose thatX1⊆X is controllable with positive probability. By Definition 3, for any state δnαi∈X2, i=l+1,⋯,n, there exist a state δnαji∈X1 and a control sequence si∈Σ∗ such that p(δnαji,si,δnαi)>0. Based on conclusion (1) of Theorem 8, one can obtain (C)αi,αji>0, i=l+1,⋯,n. Therefore, (21)∑j=1lCαi,αj≥Cαi,αji>0,∀i=l+1,⋯,n, which shows that CX1>0n-l.
(Sufficiency) Assume thatCX1>0n-l. Then for any i=l+1,⋯,n, we have ∑j=1l(C)αi,αj>0. Thus, for any state δnαi∈X2, i=l+1,⋯,n, there exist δnαji∈X1 and a control sequence si∈Σ∗ such that p(δnαji,si,δnαi)>0. By Definition 3, X1⊆X is controllable with positive probability.Theorem 11.
X 2 ⊆ X is reachable with positive probability, if and only if RX2>0l.Proof.
(Necessity) Suppose thatX2⊆X is reachable with positive probability. By Definition 4, for any state δnαj∈X1, j=1,⋯,l, there exist a state δnαij∈X2 and a control sequence sj∈Σ∗ such that p(δnαj,sj,δnαij)>0, which together with conclusion (1) of Theorem 9 implies that (C)αij,αj>0, j=1,⋯,l. Hence,(22)∑i=l+1nCαi,αj≥Cαij,αj>0,∀j=1,⋯,l. From the arbitrariness of αj, one can see that RX2>0l.
(Sufficiency) Assume thatRX2>0l. Then for any j=1,⋯,l, we have ∑i=l+1n(C)αi,αj>0. Hence, for any state δnαj∈X1, there exist δnαij∈X2 and a control sequence sj∈Σ∗ such that p(δnαj,sj,δnαij)>0. By Definition 4, X2⊆X is reachable with positive probability.Theorem 12.
X 1 ⊆ X is one-step returnable with positive probability, if and only if MX1>0l.Proof.
(Necessity) Suppose thatX1⊆X is one-step returnable with positive probability. By Definition 5, for any state δnαj∈X1, there exist a state δnαij∈X1 and an event σj∈Σ such that p(δnαj,σj,δnαij)>0. Therefore, (23)Mαij,αj>0,∀j=1,⋯,l, which implies that ∑i=1l(M)αi,αj≥(M)αij,αj>0. Thus, MX1>0l.
(Sufficiency) Assume thatMX1>0l. Then for any j=1,⋯,l, we have ∑i=1l(M)αi,αj>0. Hence, for any state δnαj∈X1, there exist δnαij∈X1 and a control sequence σj∈Σ such that p(δnαj,σj,δnαij)>0. By Definition 5, X1⊆X is one-step returnable with positive probability.Based on Definition6, Theorems 11 and 12, we have the following result on the stabilizability of PFA.Theorem 13.
X 1 ⊆ X is stabilizable with positive probability, if and only if RX1>0n-l and MX1>0l.


## 4. An Illustrate Example

In this section, we present an example to illustrate the main results.Example 14.
Consider a PFAΛ=(X,Σ,f,x0,p) shown in Figure 2, where X={x1,x2,x3,x4,x5,x6}, Σ={a,b} and x0=x1. Assume that X1={x1,x2} and X2={x3,x4,x5,x6}.Figure 2
A probabilistic finite automata.IdentifyX~Δ6={δ61,δ62,⋯,δ66} and Σ~Δ2={δ21,δ22}. The state transition probabilistic structure matrix of PFA Λ shown in Figure 2 is(24)L=L1L2=0000000000000.20.40000000000.500.400.400.50.3000000.500.50000000.60000000.5000.20000000000000.500.50,(25)whereL1=0000000.20.4000000.400.400.50.500.500000000.50000000,L2=000000000000.50.3000000000.60000.20000000.500.50.Setτ=4. Then(26)C=∑t=14Mt=0000000.50980.94460.50250.20.691.0621.15381.10460.98451.24640.741.2621.74950.6671.5582.05160.31250.80250.11540.60580.0950.021.05750.2760.47150.6780.860.4821.20.5975.By Theorem 8, the state x0=x1 is controllable to the any state except the state x1 with positive probability.A simple calculation shows thatCX1=[2.25842.41650.72121.1495], RX1=[0.50250.20.691.062], CX2=[02.4545], RX2=[3.49023.0554], MX1=[0.50980.9446], and MX2=[3.49753.83.312.938]. By Theorem 10, X1 is controllable with positive probability and X2 is not controllable with positive probability. By Theorems 11, 12, and 13, both X1 and X2 are reachable, one-step returnable, and stabilizable with positive probability, respectively.


## 5. Conclusion

In this paper, we have proposed a controllability matrix approach for the investigation of PFA via STP. Based on the controllability matrix, we have presented some necessary and sufficient conditions for the controllability, reachability, and stabilizability of PFA with positive probability. The obtained conditions are easily verified via MATLAB.



---

*Source: 8021750-2019-04-14.xml*