# Controllability, Reachability, and Stabilizability of Finite Automata: A Controllability Matrix Method

Authors: Yalu Li; Wenhui Dou; Haitao Li; Xin Liu
Journal: Mathematical Problems in Engineering
 (2018)

---

## Abstract

This paper investigates the controllability, reachability, and stabilizability of finite automata by using the semitensor product of matrices. Firstly, by expressing the states, inputs, and outputs as vector forms, an algebraic form is obtained for finite automata. Secondly, based on the algebraic form, a controllability matrix is constructed for finite automata. Thirdly, some necessary and sufficient conditions are presented for the controllability, reachability, and stabilizability of finite automata by using the controllability matrix. Finally, an illustrative example is given to support the obtained new results.


---

## Body

## 1. Introduction

In the research field of theoretical computer science, finite automaton is one of the simplest models of computation. Finite automaton is a device whose states take values from a finite set. It receives a discrete sequence of inputs from the outside world and changes its state according to the inputs. The study of finite automata has received many scholars’ research interest in the last century [1–5] due to its wide applications in engineering, computer science, and so on.As we all know, controllability and stabilizability analysis of finite automata are fundamental topics, which are important and necessary to the solvability of many related problems [1, 4, 6]. The concepts of controllability, reachability, and stabilizability of finite automata were defined in [2] by resorting to the classic control theory. The controllability of a deterministic Rabin automaton was studied in [7] by defining the “controllability subset.” Kobayashi et al. [8] investigated the state feedback stabilization of a deterministic finite automaton and presented some new results.Recently, a new matrix product, namely, the semitensor product (STP) of matrices, has been proposed by Cheng et al. [9]. Up to now, STP has been successfully applied to many research fields related to finite-valued systems like Boolean networks [10–20], multivalued logical networks [21–23], game theory [24, 25], finite automata [5, 26], and so on [27–35]. The main feature of STP is to convert a finite-valued system into an equivalent algebraic form [22]. Thus, STP provides a convenient way for the construction and analysis of finite automata [5, 26]. Xu and Hong [5] provided a matrix-based algebraic approach for the reachability analysis of finite automata with the help of STP. Yan et al. [26] studied the controllability and stabilizability analysis of finite automata based on STP and presented some novel results. It should be pointed out that although the concepts of controllability, reachability, and stabilizability of finite automata come from classic control theory, there exist fewer results on the construction of controllability matrix for finite automata.In this paper, we investigate the controllability, reachability, and stabilizability of deterministic finite automata by using STP. The main contribution of this paper is to construct a controllability matrix for finite automata based on the algebraic form. Using the controllability matrix, we present some necessary and sufficient conditions for the controllability, reachability, and stabilizability of finite automata. Compared with the existing results [5, 26], our results are more easily verified via MATLAB.The rest of this paper is organized as follows. Section2 contains some necessary preliminaries on the semitensor product of matrices and finite automata. Section 3 studies the controllability, reachability, and stabilizability of finite automata and presents the main results of this paper. In Section 4, an illustrative example is given to support our new results, which is followed by a brief conclusion in Section 5.Notations. R, N, and Z+ denote the set of real numbers, the set of natural numbers, and the set of positive integers, respectively. Δn≔{δnk:k=1,…,n}, where δnk denotes the kth column of the n×n identity matrix In. An n×t matrix M is called a logical matrix, if M=δni1δni2⋯δnit, which is briefly denoted by M=δni1i2⋯it. The set of n×t logical matrices is denoted by Ln×t. Given a real matrix A, Coli(A), Rowj(A), and (A)i,j denote the ith column, the jth row, and the (i,j)th element of A, respectively. A>0 if and only if (A)i,j>0 holds for any i,j. Blki(A) denote the ith block of an n×mn matrix A.


## 2. Preliminaries

### 2.1. Semitensor Product of Matrices

In this part, we recall some necessary preliminaries on STP. For details, please refer to [9].Definition 1.
Given two matricesA∈Rm×n and B∈Rp×q, the semitensor product of A and B is defined as (1)A⋉B=A⊗Iα/nB⊗Iα/p,where α=lcm(n,p) is the least common multiple of n and p and ⊗ is the Kronecker product of matrices.Lemma 2.
STP has the following properties:(1)
LetX∈Rt×1 be a column vector and A∈Rm×n. Then (2)X⋉A=It⊗A⋉X.(2)
LetX∈Rm×1 and Y∈Rn×1 be two column vectors. Then (3)Y⋉X=Wm,n⋉X⋉Y,whereW[m,n]∈Lmn×mn is called the swap matrix.


### 2.2. Finite Automata

In this subsection, we recall some definitions of finite automata.A finite automaton is a seven-tupleA=(X,U,Y,f,g,x0,Xm), in which X, U, and Y are finite sets of states, input symbols, and outputs, respectively; x0 and Xm⊂X are the initial state and the set of accepted states; f and g are transition and output functions, which are defined as f:X×U→2X and g:X×U→2Y, where 2X and 2Y denote the power set of X and Y, respectively; that is, f(x,u)⊂X, g(x,u)⊂Y. U∗ represents the finite string set on U, which does not include the empty transition. Given an initial state x0∈X and an input symbol u∈U, the function f uniquely determines the next subset of states, that is, f(x0,u)⊂X, while the function g uniquely determines the next subset of outputs; that is, g(x0,u)⊂Y.Throughout this paper, we only consider the deterministic finite automata; that is,fx,u≤1 holds for any x∈X and u∈U. In addition, we only investigate the controllability, reachability, and stabilizability of deterministic finite automata, and thus we do not use Y and g in the seven-tuple A=(X,U,Y,f,g,x0,Xm).In the following, we recall the definitions of controllability, reachability, and stabilizability for deterministic finite automata.Definition 3.
(i) A statexp∈X is said to be controllable to xq∈X, if there exists a control sequence ut∈U∗ such that f(xp,ut)=xq.
(ii) A statexp∈X is said to be controllable, if xp∈X is controllable to any state xq∈X.Definition 4.
(i) A statexq∈X is said to be reachable from xp∈X, if there exists a control sequence ut∈U∗ such that f(xp,ut)=xq.
(ii) A statexq∈X is said to be reachable, if xq⊂X is reachable from any state xp∈X.Given two nonempty setsX1⊆X and X2⊆X satisfying X1∪X2=X and X1∩X2=∅, we have the following definitions.Definition 5.
A nonempty set of stateX1⊆X is said to be controllable, if, for any state xq∈X2, there exist an xp∈X1 and a control sequence ut∈U∗ such that f(xp,ut)=xq.Definition 6.
A nonempty set of stateX2⊆X is said to be reachable, if, for any state xp∈X1, there exist an xq∈X2 and a control sequence ut∈U∗ such that f(xp,ut)=xq.Definition 7.
A nonempty set of stateX1⊆X is said to be 1-step returnable, if, for any state x0=xp∈X1, there exists an input ui∈U such that f(xp,ui)=xs∈X1.Definition 8.
A nonempty set of stateX1⊆X is said to be stabilizable, if X1 is reachable and 1-step returnable.


## 2.1. Semitensor Product of Matrices

In this part, we recall some necessary preliminaries on STP. For details, please refer to [9].Definition 1.
Given two matricesA∈Rm×n and B∈Rp×q, the semitensor product of A and B is defined as (1)A⋉B=A⊗Iα/nB⊗Iα/p,where α=lcm(n,p) is the least common multiple of n and p and ⊗ is the Kronecker product of matrices.Lemma 2.
STP has the following properties:(1)
LetX∈Rt×1 be a column vector and A∈Rm×n. Then (2)X⋉A=It⊗A⋉X.(2)
LetX∈Rm×1 and Y∈Rn×1 be two column vectors. Then (3)Y⋉X=Wm,n⋉X⋉Y,whereW[m,n]∈Lmn×mn is called the swap matrix.


## 2.2. Finite Automata

In this subsection, we recall some definitions of finite automata.A finite automaton is a seven-tupleA=(X,U,Y,f,g,x0,Xm), in which X, U, and Y are finite sets of states, input symbols, and outputs, respectively; x0 and Xm⊂X are the initial state and the set of accepted states; f and g are transition and output functions, which are defined as f:X×U→2X and g:X×U→2Y, where 2X and 2Y denote the power set of X and Y, respectively; that is, f(x,u)⊂X, g(x,u)⊂Y. U∗ represents the finite string set on U, which does not include the empty transition. Given an initial state x0∈X and an input symbol u∈U, the function f uniquely determines the next subset of states, that is, f(x0,u)⊂X, while the function g uniquely determines the next subset of outputs; that is, g(x0,u)⊂Y.Throughout this paper, we only consider the deterministic finite automata; that is,fx,u≤1 holds for any x∈X and u∈U. In addition, we only investigate the controllability, reachability, and stabilizability of deterministic finite automata, and thus we do not use Y and g in the seven-tuple A=(X,U,Y,f,g,x0,Xm).In the following, we recall the definitions of controllability, reachability, and stabilizability for deterministic finite automata.Definition 3.
(i) A statexp∈X is said to be controllable to xq∈X, if there exists a control sequence ut∈U∗ such that f(xp,ut)=xq.
(ii) A statexp∈X is said to be controllable, if xp∈X is controllable to any state xq∈X.Definition 4.
(i) A statexq∈X is said to be reachable from xp∈X, if there exists a control sequence ut∈U∗ such that f(xp,ut)=xq.
(ii) A statexq∈X is said to be reachable, if xq⊂X is reachable from any state xp∈X.Given two nonempty setsX1⊆X and X2⊆X satisfying X1∪X2=X and X1∩X2=∅, we have the following definitions.Definition 5.
A nonempty set of stateX1⊆X is said to be controllable, if, for any state xq∈X2, there exist an xp∈X1 and a control sequence ut∈U∗ such that f(xp,ut)=xq.Definition 6.
A nonempty set of stateX2⊆X is said to be reachable, if, for any state xp∈X1, there exist an xq∈X2 and a control sequence ut∈U∗ such that f(xp,ut)=xq.Definition 7.
A nonempty set of stateX1⊆X is said to be 1-step returnable, if, for any state x0=xp∈X1, there exists an input ui∈U such that f(xp,ui)=xs∈X1.Definition 8.
A nonempty set of stateX1⊆X is said to be stabilizable, if X1 is reachable and 1-step returnable.


## 3. Main Results

In this section, we investigate the controllability, reachability, and stabilizability of deterministic finite automata by constructing a controllability matrix.


### 3.1. Controllability Matrix

For a deterministic finite automatonA=(X,U,Y,f,g,x0,Xm), where X={x1,…,xn} and U={u1,…,um}, we identify xi as δni(i=1,…,n) and call δni the vector form of xi. Then, X can be denoted as Δn; that is, X={δn1,…,δnn}. Similarly, for U, we identify uj with δmj(j=1,…,m) and call δmj the vector form of uj. Then, U={δm1,…,δmm}.Using the vector form of elements inX and U, Yan et al. [26] construct the transition structure matrix (TSM) of A=(X,U,Y,f,g,x0,Xm) as F=F1⋯Fm. One can see that if there exists a control uj∈U which moves state xp to state xq, then (4)δnq=F⋉δmj⋉δnp.In this case, (Fj)q,p=1. Otherwise, (Fj)q,p=0. Thus, setting (5)M=∑j=1mFj∈Rn×n,then one can use M to judge whether or not state xp is controllable to state xq in one step. Precisely, state xp is controllable to state xq in one step, if and only if (M)q,p>0.Now, we show that, for anyt∈Z+, state xp is controllable to state xq at the tth step, if and only if (Mt)q,p>0. We prove it by induction. Obviously, when t=1, the conclusion holds. Assume that the conclusion holds for some t∈Z+. Then, for the case of t+1, state xp is controllable to state xq at the (t+1)th step, if and only if there exists some state xr∈X such that state xp is controllable to state xr at the tth step and state xr is controllable to state xq in one step. Hence, (6)Mt+1q,p=∑i=1nMq,iMti,p≥Mq,rMtr,p>0.By induction, for any t∈Z+, state xp is controllable to state xq at the tth step, if and only if (Mt)q,p>0. Thus, ∑t=1∞Mt contains all the controllability information of the finite automata. Noticing that M is an n×n square matrix, by Cayley-Hamilton theorem, we only need to consider t≤n. Then, we define the controllability matrix for finite automata as follows.Definition 9.
SetM=∑j=1mFj∈Rn×n. The controllability matrix of finite automata is C=∑t=1nMt.Based on the controllability matrix, we have the following result.Algorithm 10.
Consider the finite automataA=(X,U,Y,f,g,x0,Xm). Then, the controls which force xp to xq in the shortest time l can be designed by the following steps: (1)
Find the smallest integerl such that, for (7)F0l≔Ml-1F=Blk1F0lBlk2F0l⋯BlkmF0l,there exists a block, say,Blkθ(F0l), satisfying [Blkθ(F0l)]q,p>0.(2)
Setu(0)=δmθ and xq=δnq. If l=1, stop. Otherwise, go to Step (3).(3)
Findr and η such that [Blkη(F01)]q,r>0 and [Blkθ(F0l-1)]r,p>0, where F01=F and F0l-1=Ml-2F. Set u(l-1)=δmη and x(l-1)=δnr.(4)
Ifl-1=1, stop. Otherwise, replace l and q by l-1 and r, respectively, and go to Step (3).Example 11.
Consider a finite automatonA=(X,U,Y,f,g,x0,Xm) given in Figure 1, where X={x1,x2,x3}, U={1,2}. Suppose that x0=x1 and Xm={x3}. Then, X can be denoted as Δ3={δ31,δ32,δ33}. Similarly, U=Δ2={δ21,δ22}, x0=δ33, Xm={δ32}.Figure 1
A finite automata.The transition structure matrix of the finite automataA is (8)F=δ3231313.Split F=F1F2, where F1=δ3231 and F2=δ3313. Then, (9)M=011100111.Thus, the controllability matrix is (10)C=∑t=13Mt=455322777.By Algorithm 10, one can obtain that [Blk1(F02)]2,3>0. Setting xp=δ33, u(0)=δ21, and xq=δ32, one can find r=1 and η=1 such that [Blk1(F01)]2,1>0 and [Blk1(F01)]1,3>0. Let u(1)=δ21 and x1=δ31. Hence, state x3 is controllable to state x2 at the 2nd step.


### 3.2. Controllability, Reachability, and Stabilizability

In this part, we study the controllability, reachability, and stabilizability of deterministic finite automata based on the controllability matrix.According to the meaning of controllability matrix, we have the following results.Theorem 12.
The statexp∈X is controllable, if and only if (11)ColpC>0.Proof.
Necessity. Suppose that the state xp∈X is controllable. By Definition 3, xp∈X is controllable to any state xq∈X. Based on (4), one can see that there exists a control sequence {uiα:α=0,…,s-1}⊆U(1≤s≤n) satisfying δnq=Fis-1⋯Fi0⋉δnp. Thus, (Fis-1⋯Fi0)q,p>0, which implies that (12)Cq,p≥Fis-1⋯Fi0q,p>0.From the arbitrariness of q, we have Colp(C)>0.
Sufficiency. Suppose that Colp(C)>0 holds. Then, for any state xq∈X, one can find some (Fis-1⋯Fi0)q,p>0. Therefore, under the control sequence {uiα:α=0,…,s-1}⊆U, the state xp⊂X is controllable to xq∈X. From the arbitrariness of q, the state xp∈X is controllable.Theorem 13.
The statexq∈X is reachable, if and only if (13)RowqC>0.Proof.
Necessity. Suppose that the state xq∈X is reachable. By Definition 4, xq∈X is reachable to any state xp∈X. One can obtain from (4) that there exists a control sequence {uiα:α=0,…,s-1}⊆U(1≤s≤n) satisfying δnq=Fis-1⋯Fi0⋉δnp. Thus, (Fis-1⋯Fi0)q,p>0, which shows that (14)Cq,p≥Fis-1⋯Fi0q,p>0.From the arbitrariness of p, one can conclude that Rowq(C)>0.
Sufficiency. Suppose that Rowq(C)>0. Then, for any state xp∈X, there exists some (Fis-1⋯Fi0)q,p>0. Hence, under the control sequence {uiα:α=0,…,s-1}⊆U, the state xq⊂X is reachable to xp∈X. By Definition 4, the state xq∈X is reachable.Given two nonempty setsX1={δnp1,…,δnps} and X2={δnps+1,…,δnpn}, where X1∪X2=X and X1∩X2=∅, define (15)CX1=∑β=1sCps+1,pβ⋯∑β=1sCpn,pβ,RX2=∑γ=s+1nCpγ,p1⋯∑γ=s+1nCpγ,ps.Based on Theorems 12 and 13, we have the following result.Theorem 14.
(i) The nonempty setX1⊆X is controllable, if and only if CX1>0.
(ii) The nonempty setX2⊆X is reachable, if and only if RX2>0.Proof.
(i) Necessity. Suppose that the nonempty set X1⊆X is controllable. By Definition 5, for any state δnpγ∈X2, there exist a δnpβ∈X1 and a control sequence ut∈U∗ such that f(δnpβ,ut)=δnpγ. Based on Theorems 12 and 13, for a fixed δnpγ∈X2, γ=s+1,s+2,…,n, at least one of the following cases is true: (C)pγ,p1>0,(C)pγ,p2>0,…,(C)pγ,ps>0. Therefore, for a fixed δnpγ∈X2, one can conclude that ∑β=1s(C)pγ,pβ>0. From the arbitrariness of pγ, one can see that (16)CX1=∑β=1sCps+1,pβ⋯∑β=1sCpn,pβ>0.
Sufficiency. Suppose that CX1=∑β=1s(C)ps+1,pβ⋯∑β=1s(C)pn,pβ>0. Then, for any γ=s+1,…,n, we have ∑β=1s(C)pγ,pβ>0. It means that, for any state δnpγ∈X2, there exist a δnpβ∈X1 and a control sequence ut∈U∗ such that f(δnpβ,ut)=δnpγ. By Definition 5, the nonempty set X1⊆X is controllable.
(ii) Necessity. Suppose that the nonempty set X2⊆X is reachable. By Definition 6, for any state δnpβ∈X1, there exist a δnpγ∈X2 and a control sequence ut∈U∗ such that f(δnpβ,ut)=δnpγ. Based on Theorems 12 and 13, for a fixed δnpβ∈X1, β=1,2,…,s, at least one of the following cases is true: (C)ps+1,pβ>0,(C)ps+2,pβ>0,…,(C)pn,pβ>0. Therefore, for a fixed δnpβ∈X1, one can see that ∑γ=s+1n(C)pγ,pβ>0. From the arbitrariness of pβ, we have (17)∑γ=s+1nCpγ,p1⋯∑γ=s+1nCpγ,ps>0.
Sufficiency. Suppose that ∑γ=s+1n(C)pγ,p1⋯∑γ=s+1n(C)pγ,ps>0. Then, for any β=1,2,…,s, we have ∑γ=s+1n(C)pγ,pβ>0. It means that, for any state δnpβ∈X1, there exist a δnpγ∈X2 and a control sequence ut∈U∗ such that f(δnpβ,ut)=δnpγ. By Definition 6, the nonempty set X2⊆X is reachable.Finally, we study the stabilizability of deterministic finite automata.ForX1={δnp1,…,δnps} and X2={δnps+1,…,δnpn}, define (18)MX1=∑i=1sMpi,p1⋯∑i=1sMpi,ps.Theorem 15.
The nonempty setX1⊆X is 1-step returnable, if and only if MX1>0.Proof.
By Definition7, one can see that the nonempty set X1⊆X is 1-step returnable, if and only if, for any state δnpβ∈X1, there exist an input ui∈U and some δnpi∈X1 such that f(δnpβ,ui)=δnpi, that is, for a fixed δnpβ∈X1, β=1,2,…,s, at least one of the following cases is true: (M)p1,pβ>0,(M)p2,pβ>0,…,(M)ps,pβ>0. Hence, ∑i=1s(M)pi,pβ>0, ∀β=1,…,s. From the arbitrariness of pβ, one can obtain that MX1>0.Based on Theorems14 and 15, we have the following result.Corollary 16.
The nonempty setX1⊆X is stabilizable, if and only if MX1>0 and RX1>0.Proof.
By Definition8, X1⊆X is stabilizable, if and only if X1 is reachable and 1-step returnable. Based on Theorems 14 and 15, the conclusion follows.Remark 17.
Compared with the existing results on the controllability and stabilizability of deterministic finite automata [5, 26], the main advantage of our results is to propose a unified tool, that is, controllability matrix, for the study of deterministic finite automata. The new conditions are more easily verified via MATLAB.


## 3.1. Controllability Matrix

For a deterministic finite automatonA=(X,U,Y,f,g,x0,Xm), where X={x1,…,xn} and U={u1,…,um}, we identify xi as δni(i=1,…,n) and call δni the vector form of xi. Then, X can be denoted as Δn; that is, X={δn1,…,δnn}. Similarly, for U, we identify uj with δmj(j=1,…,m) and call δmj the vector form of uj. Then, U={δm1,…,δmm}.Using the vector form of elements inX and U, Yan et al. [26] construct the transition structure matrix (TSM) of A=(X,U,Y,f,g,x0,Xm) as F=F1⋯Fm. One can see that if there exists a control uj∈U which moves state xp to state xq, then (4)δnq=F⋉δmj⋉δnp.In this case, (Fj)q,p=1. Otherwise, (Fj)q,p=0. Thus, setting (5)M=∑j=1mFj∈Rn×n,then one can use M to judge whether or not state xp is controllable to state xq in one step. Precisely, state xp is controllable to state xq in one step, if and only if (M)q,p>0.Now, we show that, for anyt∈Z+, state xp is controllable to state xq at the tth step, if and only if (Mt)q,p>0. We prove it by induction. Obviously, when t=1, the conclusion holds. Assume that the conclusion holds for some t∈Z+. Then, for the case of t+1, state xp is controllable to state xq at the (t+1)th step, if and only if there exists some state xr∈X such that state xp is controllable to state xr at the tth step and state xr is controllable to state xq in one step. Hence, (6)Mt+1q,p=∑i=1nMq,iMti,p≥Mq,rMtr,p>0.By induction, for any t∈Z+, state xp is controllable to state xq at the tth step, if and only if (Mt)q,p>0. Thus, ∑t=1∞Mt contains all the controllability information of the finite automata. Noticing that M is an n×n square matrix, by Cayley-Hamilton theorem, we only need to consider t≤n. Then, we define the controllability matrix for finite automata as follows.Definition 9.
SetM=∑j=1mFj∈Rn×n. The controllability matrix of finite automata is C=∑t=1nMt.Based on the controllability matrix, we have the following result.Algorithm 10.
Consider the finite automataA=(X,U,Y,f,g,x0,Xm). Then, the controls which force xp to xq in the shortest time l can be designed by the following steps: (1)
Find the smallest integerl such that, for (7)F0l≔Ml-1F=Blk1F0lBlk2F0l⋯BlkmF0l,there exists a block, say,Blkθ(F0l), satisfying [Blkθ(F0l)]q,p>0.(2)
Setu(0)=δmθ and xq=δnq. If l=1, stop. Otherwise, go to Step (3).(3)
Findr and η such that [Blkη(F01)]q,r>0 and [Blkθ(F0l-1)]r,p>0, where F01=F and F0l-1=Ml-2F. Set u(l-1)=δmη and x(l-1)=δnr.(4)
Ifl-1=1, stop. Otherwise, replace l and q by l-1 and r, respectively, and go to Step (3).Example 11.
Consider a finite automatonA=(X,U,Y,f,g,x0,Xm) given in Figure 1, where X={x1,x2,x3}, U={1,2}. Suppose that x0=x1 and Xm={x3}. Then, X can be denoted as Δ3={δ31,δ32,δ33}. Similarly, U=Δ2={δ21,δ22}, x0=δ33, Xm={δ32}.Figure 1
A finite automata.The transition structure matrix of the finite automataA is (8)F=δ3231313.Split F=F1F2, where F1=δ3231 and F2=δ3313. Then, (9)M=011100111.Thus, the controllability matrix is (10)C=∑t=13Mt=455322777.By Algorithm 10, one can obtain that [Blk1(F02)]2,3>0. Setting xp=δ33, u(0)=δ21, and xq=δ32, one can find r=1 and η=1 such that [Blk1(F01)]2,1>0 and [Blk1(F01)]1,3>0. Let u(1)=δ21 and x1=δ31. Hence, state x3 is controllable to state x2 at the 2nd step.


## 3.2. Controllability, Reachability, and Stabilizability

In this part, we study the controllability, reachability, and stabilizability of deterministic finite automata based on the controllability matrix.According to the meaning of controllability matrix, we have the following results.Theorem 12.
The statexp∈X is controllable, if and only if (11)ColpC>0.Proof.
Necessity. Suppose that the state xp∈X is controllable. By Definition 3, xp∈X is controllable to any state xq∈X. Based on (4), one can see that there exists a control sequence {uiα:α=0,…,s-1}⊆U(1≤s≤n) satisfying δnq=Fis-1⋯Fi0⋉δnp. Thus, (Fis-1⋯Fi0)q,p>0, which implies that (12)Cq,p≥Fis-1⋯Fi0q,p>0.From the arbitrariness of q, we have Colp(C)>0.
Sufficiency. Suppose that Colp(C)>0 holds. Then, for any state xq∈X, one can find some (Fis-1⋯Fi0)q,p>0. Therefore, under the control sequence {uiα:α=0,…,s-1}⊆U, the state xp⊂X is controllable to xq∈X. From the arbitrariness of q, the state xp∈X is controllable.Theorem 13.
The statexq∈X is reachable, if and only if (13)RowqC>0.Proof.
Necessity. Suppose that the state xq∈X is reachable. By Definition 4, xq∈X is reachable to any state xp∈X. One can obtain from (4) that there exists a control sequence {uiα:α=0,…,s-1}⊆U(1≤s≤n) satisfying δnq=Fis-1⋯Fi0⋉δnp. Thus, (Fis-1⋯Fi0)q,p>0, which shows that (14)Cq,p≥Fis-1⋯Fi0q,p>0.From the arbitrariness of p, one can conclude that Rowq(C)>0.
Sufficiency. Suppose that Rowq(C)>0. Then, for any state xp∈X, there exists some (Fis-1⋯Fi0)q,p>0. Hence, under the control sequence {uiα:α=0,…,s-1}⊆U, the state xq⊂X is reachable to xp∈X. By Definition 4, the state xq∈X is reachable.Given two nonempty setsX1={δnp1,…,δnps} and X2={δnps+1,…,δnpn}, where X1∪X2=X and X1∩X2=∅, define (15)CX1=∑β=1sCps+1,pβ⋯∑β=1sCpn,pβ,RX2=∑γ=s+1nCpγ,p1⋯∑γ=s+1nCpγ,ps.Based on Theorems 12 and 13, we have the following result.Theorem 14.
(i) The nonempty setX1⊆X is controllable, if and only if CX1>0.
(ii) The nonempty setX2⊆X is reachable, if and only if RX2>0.Proof.
(i) Necessity. Suppose that the nonempty set X1⊆X is controllable. By Definition 5, for any state δnpγ∈X2, there exist a δnpβ∈X1 and a control sequence ut∈U∗ such that f(δnpβ,ut)=δnpγ. Based on Theorems 12 and 13, for a fixed δnpγ∈X2, γ=s+1,s+2,…,n, at least one of the following cases is true: (C)pγ,p1>0,(C)pγ,p2>0,…,(C)pγ,ps>0. Therefore, for a fixed δnpγ∈X2, one can conclude that ∑β=1s(C)pγ,pβ>0. From the arbitrariness of pγ, one can see that (16)CX1=∑β=1sCps+1,pβ⋯∑β=1sCpn,pβ>0.
Sufficiency. Suppose that CX1=∑β=1s(C)ps+1,pβ⋯∑β=1s(C)pn,pβ>0. Then, for any γ=s+1,…,n, we have ∑β=1s(C)pγ,pβ>0. It means that, for any state δnpγ∈X2, there exist a δnpβ∈X1 and a control sequence ut∈U∗ such that f(δnpβ,ut)=δnpγ. By Definition 5, the nonempty set X1⊆X is controllable.
(ii) Necessity. Suppose that the nonempty set X2⊆X is reachable. By Definition 6, for any state δnpβ∈X1, there exist a δnpγ∈X2 and a control sequence ut∈U∗ such that f(δnpβ,ut)=δnpγ. Based on Theorems 12 and 13, for a fixed δnpβ∈X1, β=1,2,…,s, at least one of the following cases is true: (C)ps+1,pβ>0,(C)ps+2,pβ>0,…,(C)pn,pβ>0. Therefore, for a fixed δnpβ∈X1, one can see that ∑γ=s+1n(C)pγ,pβ>0. From the arbitrariness of pβ, we have (17)∑γ=s+1nCpγ,p1⋯∑γ=s+1nCpγ,ps>0.
Sufficiency. Suppose that ∑γ=s+1n(C)pγ,p1⋯∑γ=s+1n(C)pγ,ps>0. Then, for any β=1,2,…,s, we have ∑γ=s+1n(C)pγ,pβ>0. It means that, for any state δnpβ∈X1, there exist a δnpγ∈X2 and a control sequence ut∈U∗ such that f(δnpβ,ut)=δnpγ. By Definition 6, the nonempty set X2⊆X is reachable.Finally, we study the stabilizability of deterministic finite automata.ForX1={δnp1,…,δnps} and X2={δnps+1,…,δnpn}, define (18)MX1=∑i=1sMpi,p1⋯∑i=1sMpi,ps.Theorem 15.
The nonempty setX1⊆X is 1-step returnable, if and only if MX1>0.Proof.
By Definition7, one can see that the nonempty set X1⊆X is 1-step returnable, if and only if, for any state δnpβ∈X1, there exist an input ui∈U and some δnpi∈X1 such that f(δnpβ,ui)=δnpi, that is, for a fixed δnpβ∈X1, β=1,2,…,s, at least one of the following cases is true: (M)p1,pβ>0,(M)p2,pβ>0,…,(M)ps,pβ>0. Hence, ∑i=1s(M)pi,pβ>0, ∀β=1,…,s. From the arbitrariness of pβ, one can obtain that MX1>0.Based on Theorems14 and 15, we have the following result.Corollary 16.
The nonempty setX1⊆X is stabilizable, if and only if MX1>0 and RX1>0.Proof.
By Definition8, X1⊆X is stabilizable, if and only if X1 is reachable and 1-step returnable. Based on Theorems 14 and 15, the conclusion follows.Remark 17.
Compared with the existing results on the controllability and stabilizability of deterministic finite automata [5, 26], the main advantage of our results is to propose a unified tool, that is, controllability matrix, for the study of deterministic finite automata. The new conditions are more easily verified via MATLAB.


## 4. An Illustrative Example

Consider the finite automataA=(X,U,Y,f,g,x0,Xm) given in Figure 2, where X={x1,x2,x3,x4} and U={1,2}.Figure 2
A finite automata.From Figure2, we can see that x1→1x2→1x3→2x4 and x1→1x2→2x1. Therefore, by Definition 3, one can obtain that x1 is controllable. Similarly, by Definition 3, we conclude that x2, x3, and x4 are also controllable. By Definition 4, we can also find that all the states are reachable.Assume thatX1={x1,x2} and X2={x3,x4}. Since x1∈X1→1x2→1x3∈X2 and x1∈X1→2x4∈X2, by Definition 5, one can see that X1 is controllable. Similarly, we also obtain that X2 is controllable. Since x3→2x4→1x2→2x1 and x1→1x2→1x3→2x4, by Definition 6, we can obtain that X1 and X2 are reachable. From Figure 2, we can see that x1→1x2, x2→2x1, x3→2x4, and x4→2x3. Hence, by Definition 7, X1 and X2 are 1-step returnable. By Definition 8, the sets X1 and X2 are stabilizable.Now, we check the above properties based on the controllability matrix.The transition structure matrix of the finite automataA is (19)F=δ423324143.Split F=F1F2, where F1=δ42332 and F2=δ44143. Then, (20)M=0100100101111010.Thus, the controllability matrix is (21)C=∑t=14Mt=34237556121314148897.Since all rows and columns ofC are positive, by Theorems 12 and 13, any state xi∈X is controllable and reachable, i=1,2,3,4.A simple calculation givesCX1=2516, RX1=79, CX2=511, RX2=2021, MX1=109, and MX2=2321. By Theorems 14 and 15 and Corollary 16, X1 and X2 are controllable, reachable, 1-step returnable, and stabilizable, respectively.


## 5. Conclusion

In this paper, we have investigated the controllability, reachability, and stabilizability of deterministic finite automata by using the semitensor product of matrices. We have obtained the algebraic form of finite automata by expressing the states, inputs, and outputs as vector forms. Based on the algebraic form, we have defined the controllability matrix for deterministic finite automata. In addition, using the controllability matrix, we have presented several necessary and sufficient conditions for the controllability, reachability, and stabilizability of finite automata. The study of an illustrative example has shown that the obtained new results are effective.



---

*Source: 6719319-2018-02-28.xml*