有穷状态机课件

图4.1保险箱的状态转换图有穷状态机课件1图4.1是一个有穷状态机的状态转换图。从上面这个简单例子可以看出，一个有穷状态机包括下述5个部分：状态集J、输入集K、由当前状态和当前输入确定下一个状态(次态)的转换函数T、初始态S和终态集F。对于保险箱的例子，相应的有穷状态机的各部分如下。状态集J：｛保险箱锁定，A，B，保险箱解锁，报警｝。输入集K：｛1L，1R，2L，2R，3L，3R｝。图4.1是一个有穷状态机的状态转换图。2转换函数T：如表4.1所示。初始态S：保险箱锁定。终态集F：｛保险箱解锁，报警｝。一个有穷状态机可以表示为一个5元组(J，K，T，S，F)，其中：J是一个有穷的非空状态集；K是一个有穷的非空输入集；T是一个从(J-F)×K到J的转换函数；?S∈J，是一个初始状态；FJ，是终态集。转换函数T：如表4.1所示。3一个保险箱上装了一个复合锁，锁有三个位置，分别标记为1、2、3，转盘可向左(L)或向右(R)转动。这样，在任意时刻转盘都有6种可能的运动，即1L、1R、2L、2R、3L和3R。保险箱的组合密码是1L、3R、2L，转盘的任何其他运动都将引起报警，请画出相应状态转换图。思考题一个保险箱上装了一个复合锁，锁有三个位置，分别标记为1、2、4有穷状态机方法采用了一种简单的格式来描述规格说明：当前状态+事件+(谓词)下个状态这种形式的规格说明易于书写、易于验证，而且可以比较容易地把它转变成设计或程序代码。事实上，可以开发一个CASE工具把一个有穷状态机规格说明直接转变为源代码。4.2.3评价有穷状态机方法采用了一种简单的格式来描述规格说明：4.2.35有限自动机有限自动机（FA）是更一般化的状态转换图，它分为确定有限自动机DFA和非确定有限自动机NFA两种。

1．确定有限自动机（DFA）一个确定的有限自动机Md（记为DFAMd）是一个五元组Md=（S,Σ,f,s0,Z），其中：

(1)S是一个有限状态集，它的每一个元素称为一个状态；

(2)Σ是一个有穷输入字母表，它的每一个元素称为一个输入字符；有限自动机6

(3)f是一个从S×Σ到S的单值映射即

f(si,a)=sj且有si、sj∈S和a∈Σ；

(4)s0∈S，是惟一的一个初态；

(5)ZS，是一个终态集。例如，对下图所给出的状态s1有：

f(s1,a)=s2f(s1,b)=s3f(s1,c)=s4因此，f是单值映射函数。(3)f是一个从S×Σ到S的单值7图DFA的状态转换示意图DFA的状态转换示意8DFA又例：DFAM=（{S,U,V,Q},{a,b},f,S,{Q}）其中f定义为：f（S，a）=U f（V，a）=Uf（S，b）=V f（v，b）=Qf（U，a）=Q f（Q，a）=Qf（U，b）=V f（Q，b）=QDFA又例：DFAM=（{S,U,V,Q},{a,9DFA的状态图表示f（S，a）=U f（V，a）=Uf（S，b）=V f（v，b）=Qf（U，a）=Q f（Q，a）=Qf（U，b）=V f（Q，b）=QbSUVQaaaba，bbDFA的状态图表示f（S，a）=U f（V，a）=UbS10DFA的矩阵表示f（S，a）=U f（V，a）=Uf（S，b）=V f（v，b）=Qf（U，a）=Q f（Q，a）=Qf（U，b）=V f（Q，b）=Q字符状态DFA的矩阵表示f（S，a）=U f（V，a）=U字符状112．非确定有限自动机(NFA)

一个非确定有限自动机Mn(记为NFAMn)

是一个五元组Mn=(S,Σ,f,s0,Z)，其中：

(1)S是一个有限状态集，它的每一个元素称为一个状态；

(2)Σ是一个有穷输入字母表，它的每一个元素称为一个输入字符；

(3)f是一个从S×Σ到S的子集映射；

(4)s0∈S，是惟一的一个初态；

(5)ZS，是一个终态集。

2．非确定有限自动机(NFA)12

NFA和DFA的区别主要是：NFA的状态转换函数f不是单值函数，而是一个多值函数，即f(si，a)={某些状态的集合}（si∈S），它表示不能由当前状态和当前输入字符惟一地确定下一个要转换的状态，也即允许同一个状态对同一个输入字符可以有不同的输出边。NFA和DFA的区别主要是：NFA的13图NFA的状态转换示意图NFA的状态转换示意14例如，对上图所给出的状态s1有：

f(s1,

a)={s1,s2,s3}

即f是一个从S×Σ*到S的子集映射；Σ*表示输出边上所标记的不仅是字符，也可以是字。此外，NFA还允许f(s1,ε)={某些状态的集合}，即在NFA的状态转换图中输出边上的标记还可是ε(空字)。例如，对上图所给出的状态s1有：153．状态转换图与状态转换矩阵

(1)DFA和NFA都可以用状态转换图表示。假定DFA（或NFA）有m个状态、n个输入字符（或字），则这个状态转换图含有m个状态，每个状态最多有n条输出边与其它状态相连接，每一条输出边用Σ（或Σ*）中的一个不同的输入字符（或一个输入字）作标记，整个图含有惟一一个初态和若干个终态。

(2)DFA和NFA也可以用状态转换矩阵表示。状态转换矩阵的行表示状态，列表示输入符号，矩阵元素表示f(si,

a)的值。3．状态转换图与状态转换矩阵16例假定DFAMd=({s0,s1,s2},{a,b},f,s0,{s2})且有：

f(s0，a)=s1 f(s0，b)=s2 f(s1，a)=s1 f(s1，b)=s2 f(s2，a)=s2 f(s2，b)=s1试给出DFAMd的状态转换图与状态转换矩阵。[解答]DFAMd的状态转换图和状态转换矩阵见下一张幻灯片。例假定DFAMd=({s0,s1,s2}17

字符状态abs0s1s2s1s1s2s2s2s1

DFAMd状态转换矩阵DFAMd状态转换图abs0s1s2s1s1s2s2s2s1DFAMd状态18表2.3状态转换矩阵字符状态abs0{s2}{s0，s1}s1Φ{s2}s2Φ{s1}表2.3状态转换矩阵字符abs0{s2}{s0，19图4.1保险箱的状态转换图有穷状态机课件20图4.1是一个有穷状态机的状态转换图。从上面这个简单例子可以看出，一个有穷状态机包括下述5个部分：状态集J、输入集K、由当前状态和当前输入确定下一个状态(次态)的转换函数T、初始态S和终态集F。对于保险箱的例子，相应的有穷状态机的各部分如下。状态集J：｛保险箱锁定，A，B，保险箱解锁，报警｝。输入集K：｛1L，1R，2L，2R，3L，3R｝。图4.1是一个有穷状态机的状态转换图。21转换函数T：如表4.1所示。初始态S：保险箱锁定。终态集F：｛保险箱解锁，报警｝。一个有穷状态机可以表示为一个5元组(J，K，T，S，F)，其中：J是一个有穷的非空状态集；K是一个有穷的非空输入集；T是一个从(J-F)×K到J的转换函数；?S∈J，是一个初始状态；FJ，是终态集。转换函数T：如表4.1所示。22一个保险箱上装了一个复合锁，锁有三个位置，分别标记为1、2、3，转盘可向左(L)或向右(R)转动。这样，在任意时刻转盘都有6种可能的运动，即1L、1R、2L、2R、3L和3R。保险箱的组合密码是1L、3R、2L，转盘的任何其他运动都将引起报警，请画出相应状态转换图。思考题一个保险箱上装了一个复合锁，锁有三个位置，分别标记为1、2、23有穷状态机方法采用了一种简单的格式来描述规格说明：当前状态+事件+(谓词)下个状态这种形式的规格说明易于书写、易于验证，而且可以比较容易地把它转变成设计或程序代码。事实上，可以开发一个CASE工具把一个有穷状态机规格说明直接转变为源代码。4.2.3评价有穷状态机方法采用了一种简单的格式来描述规格说明：4.2.324有限自动机有限自动机（FA）是更一般化的状态转换图，它分为确定有限自动机DFA和非确定有限自动机NFA两种。

1．确定有限自动机（DFA）一个确定的有限自动机Md（记为DFAMd）是一个五元组Md=（S,Σ,f,s0,Z），其中：

(1)S是一个有限状态集，它的每一个元素称为一个状态；

(2)Σ是一个有穷输入字母表，它的每一个元素称为一个输入字符；有限自动机25

(3)f是一个从S×Σ到S的单值映射即

f(si,a)=sj且有si、sj∈S和a∈Σ；

(4)s0∈S，是惟一的一个初态；

(5)ZS，是一个终态集。例如，对下图所给出的状态s1有：

f(s1,a)=s2f(s1,b)=s3f(s1,c)=s4因此，f是单值映射函数。(3)f是一个从S×Σ到S的单值26图DFA的状态转换示意图DFA的状态转换示意27DFA又例：DFAM=（{S,U,V,Q},{a,b},f,S,{Q}）其中f定义为：f（S，a）=U f（V，a）=Uf（S，b）=V f（v，b）=Qf（U，a）=Q f（Q，a）=Qf（U，b）=V f（Q，b）=QDFA又例：DFAM=（{S,U,V,Q},{a,28DFA的状态图表示f（S，a）=U f（V，a）=Uf（S，b）=V f（v，b）=Qf（U，a）=Q f（Q，a）=Qf（U，b）=V f（Q，b）=QbSUVQaaaba，bbDFA的状态图表示f（S，a）=U f（V，a）=UbS29DFA的矩阵表示f（S，a）=U f（V，a）=Uf（S，b）=V f（v，b）=Qf（U，a）=Q f（Q，a）=Qf（U，b）=V f（Q，b）=Q字符状态DFA的矩阵表示f（S，a）=U f（V，a）=U字符状302．非确定有限自动机(NFA)

一个非确定有限自动机Mn(记为NFAMn)

是一个五元组Mn=(S,Σ,f,s0,Z)，其中：

(1)S是一个有限状态集，它的每一个元素称为一个状态；

(2)Σ是一个有穷输入字母表，它的每一个元素称为一个输入字符；

(3)f是一个从S×Σ到S的子集映射；

(4)s0∈S，是惟一的一个初态；

(5)ZS，是一个终态集。

2．非确定有限自动机(NFA)31

NFA和DFA的区别主要是：NFA的状态转换函数f不是单值函数，而是一个多值函数，即f(si，a)={某些状态的集合}（si∈S），它表示不能由当前状态和当前输入字符惟一地确定下一个要转换的状态，也即允许同一个状态对同一个输入字符可以有不同的输出边。NFA和DFA的区别主要是：NFA的32图NFA的状态转换示意图NFA的状态转换示意33例如，对上图所给出的状态s1有：

f(s1,

a)={s1,s2,s3}

即f是一个从S×Σ*到S的子集映射；Σ*表示输出边上所标记的不仅是字符，也可以是字。此外，NFA还允许f(s1,ε)={某些状态的集合}，即在NFA的状态转换图中输出边上的标记还可是ε(空字)。例如，对上图所给出的状态s1有：343．状态转换图与状态转换矩阵

(1)DFA和NFA都可以用状态转换图表示。假定DFA（或NFA）有m个状态、n个输入字符（或字），则这个状态转换图含有m个状态，每个状态最多有n条输出边与其它状态相连接，每一条输出边用Σ（或Σ*）中的一个不