有窮狀態(tài)機(jī)課件

圖4.1保險(xiǎn)箱的狀態(tài)轉(zhuǎn)換圖有窮狀態(tài)機(jī)課件1圖4.1是一個(gè)有窮狀態(tài)機(jī)的狀態(tài)轉(zhuǎn)換圖。從上面這個(gè)簡(jiǎn)單例子可以看出，一個(gè)有窮狀態(tài)機(jī)包括下述5個(gè)部分：狀態(tài)集J、輸入集K、由當(dāng)前狀態(tài)和當(dāng)前輸入確定下一個(gè)狀態(tài)(次態(tài))的轉(zhuǎn)換函數(shù)T、初始態(tài)S和終態(tài)集F。對(duì)于保險(xiǎn)箱的例子，相應(yīng)的有窮狀態(tài)機(jī)的各部分如下。狀態(tài)集J：｛保險(xiǎn)箱鎖定，A，B，保險(xiǎn)箱解鎖，報(bào)警｝。輸入集K：｛1L，1R，2L，2R，3L，3R｝。圖4.1是一個(gè)有窮狀態(tài)機(jī)的狀態(tài)轉(zhuǎn)換圖。2轉(zhuǎn)換函數(shù)T：如表4.1所示。初始態(tài)S：保險(xiǎn)箱鎖定。終態(tài)集F：｛保險(xiǎn)箱解鎖，報(bào)警｝。一個(gè)有窮狀態(tài)機(jī)可以表示為一個(gè)5元組(J，K，T，S，F(xiàn))，其中：J是一個(gè)有窮的非空狀態(tài)集；K是一個(gè)有窮的非空輸入集；T是一個(gè)從(J-F)×K到J的轉(zhuǎn)換函數(shù)；?S∈J，是一個(gè)初始狀態(tài)；FJ，是終態(tài)集。轉(zhuǎn)換函數(shù)T：如表4.1所示。3一個(gè)保險(xiǎn)箱上裝了一個(gè)復(fù)合鎖，鎖有三個(gè)位置，分別標(biāo)記為1、2、3，轉(zhuǎn)盤可向左(L)或向右(R)轉(zhuǎn)動(dòng)。這樣，在任意時(shí)刻轉(zhuǎn)盤都有6種可能的運(yùn)動(dòng)，即1L、1R、2L、2R、3L和3R。保險(xiǎn)箱的組合密碼是1L、3R、2L，轉(zhuǎn)盤的任何其他運(yùn)動(dòng)都將引起報(bào)警，請(qǐng)畫出相應(yīng)狀態(tài)轉(zhuǎn)換圖。思考題一個(gè)保險(xiǎn)箱上裝了一個(gè)復(fù)合鎖，鎖有三個(gè)位置，分別標(biāo)記為1、2、4有窮狀態(tài)機(jī)方法采用了一種簡(jiǎn)單的格式來描述規(guī)格說明：當(dāng)前狀態(tài)+事件+(謂詞)下個(gè)狀態(tài)這種形式的規(guī)格說明易于書寫、易于驗(yàn)證，而且可以比較容易地把它轉(zhuǎn)變成設(shè)計(jì)或程序代碼。事實(shí)上，可以開發(fā)一個(gè)CASE工具把一個(gè)有窮狀態(tài)機(jī)規(guī)格說明直接轉(zhuǎn)變?yōu)樵创a。4.2.3評(píng)價(jià)有窮狀態(tài)機(jī)方法采用了一種簡(jiǎn)單的格式來描述規(guī)格說明：4.2.35有限自動(dòng)機(jī)有限自動(dòng)機(jī)（FA）是更一般化的狀態(tài)轉(zhuǎn)換圖，它分為確定有限自動(dòng)機(jī)DFA和非確定有限自動(dòng)機(jī)NFA兩種。

1．確定有限自動(dòng)機(jī)（DFA）一個(gè)確定的有限自動(dòng)機(jī)Md（記為DFAMd）是一個(gè)五元組Md=（S,Σ,f,s0,Z），其中：

(1)S是一個(gè)有限狀態(tài)集，它的每一個(gè)元素稱為一個(gè)狀態(tài)；

(2)Σ是一個(gè)有窮輸入字母表，它的每一個(gè)元素稱為一個(gè)輸入字符；有限自動(dòng)機(jī)6

(3)f是一個(gè)從S×Σ到S的單值映射即

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

(4)s0∈S，是惟一的一個(gè)初態(tài)；

(5)ZS，是一個(gè)終態(tài)集。例如，對(duì)下圖所給出的狀態(tài)s1有：

f(s1,a)=s2f(s1,b)=s3f(s1,c)=s4因此，f是單值映射函數(shù)。(3)f是一個(gè)從S×Σ到S的單值7圖DFA的狀態(tài)轉(zhuǎn)換示意圖DFA的狀態(tài)轉(zhuǎn)換示意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的狀態(tài)圖表示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的狀態(tài)圖表示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字符狀態(tài)DFA的矩陣表示f（S，a）=U f（V，a）=U字符狀112．非確定有限自動(dòng)機(jī)(NFA)

一個(gè)非確定有限自動(dòng)機(jī)Mn(記為NFAMn)

是一個(gè)五元組Mn=(S,Σ,f,s0,Z)，其中：

(1)S是一個(gè)有限狀態(tài)集，它的每一個(gè)元素稱為一個(gè)狀態(tài)；

(2)Σ是一個(gè)有窮輸入字母表，它的每一個(gè)元素稱為一個(gè)輸入字符；

(3)f是一個(gè)從S×Σ到S的子集映射；

(4)s0∈S，是惟一的一個(gè)初態(tài)；

(5)ZS，是一個(gè)終態(tài)集。

2．非確定有限自動(dòng)機(jī)(NFA)12

NFA和DFA的區(qū)別主要是：NFA的狀態(tài)轉(zhuǎn)換函數(shù)f不是單值函數(shù)，而是一個(gè)多值函數(shù)，即f(si，a)={某些狀態(tài)的集合}（si∈S），它表示不能由當(dāng)前狀態(tài)和當(dāng)前輸入字符惟一地確定下一個(gè)要轉(zhuǎn)換的狀態(tài)，也即允許同一個(gè)狀態(tài)對(duì)同一個(gè)輸入字符可以有不同的輸出邊。NFA和DFA的區(qū)別主要是：NFA的13圖NFA的狀態(tài)轉(zhuǎn)換示意圖NFA的狀態(tài)轉(zhuǎn)換示意14例如，對(duì)上圖所給出的狀態(tài)s1有：

f(s1,

a)={s1,s2,s3}

即f是一個(gè)從S×Σ*到S的子集映射；Σ*表示輸出邊上所標(biāo)記的不僅是字符，也可以是字。此外，NFA還允許f(s1,ε)={某些狀態(tài)的集合}，即在NFA的狀態(tài)轉(zhuǎn)換圖中輸出邊上的標(biāo)記還可是ε(空字)。例如，對(duì)上圖所給出的狀態(tài)s1有：153．狀態(tài)轉(zhuǎn)換圖與狀態(tài)轉(zhuǎn)換矩陣

(1)DFA和NFA都可以用狀態(tài)轉(zhuǎn)換圖表示。假定DFA（或NFA）有m個(gè)狀態(tài)、n個(gè)輸入字符（或字），則這個(gè)狀態(tài)轉(zhuǎn)換圖含有m個(gè)狀態(tài)，每個(gè)狀態(tài)最多有n條輸出邊與其它狀態(tài)相連接，每一條輸出邊用Σ（或Σ*）中的一個(gè)不同的輸入字符（或一個(gè)輸入字）作標(biāo)記，整個(gè)圖含有惟一一個(gè)初態(tài)和若干個(gè)終態(tài)。

(2)DFA和NFA也可以用狀態(tài)轉(zhuǎn)換矩陣表示。狀態(tài)轉(zhuǎn)換矩陣的行表示狀態(tài)，列表示輸入符號(hào)，矩陣元素表示f(si,

a)的值。3．狀態(tài)轉(zhuǎn)換圖與狀態(tài)轉(zhuǎn)換矩陣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的狀態(tài)轉(zhuǎn)換圖與狀態(tài)轉(zhuǎn)換矩陣。[解答]DFAMd的狀態(tài)轉(zhuǎn)換圖和狀態(tài)轉(zhuǎn)換矩陣見下一張幻燈片。例假定DFAMd=({s0,s1,s2}17

字符狀態(tài)abs0s1s2s1s1s2s2s2s1

DFAMd狀態(tài)轉(zhuǎn)換矩陣DFAMd狀態(tài)轉(zhuǎn)換圖abs0s1s2s1s1s2s2s2s1DFAMd狀態(tài)18表2.3狀態(tài)轉(zhuǎn)換矩陣字符狀態(tài)abs0{s2}{s0，s1}s1Φ{s2}s2Φ{s1}表2.3狀態(tài)轉(zhuǎn)換矩陣字符abs0{s2}{s0，19圖4.1保險(xiǎn)箱的狀態(tài)轉(zhuǎn)換圖有窮狀態(tài)機(jī)課件20圖4.1是一個(gè)有窮狀態(tài)機(jī)的狀態(tài)轉(zhuǎn)換圖。從上面這個(gè)簡(jiǎn)單例子可以看出，一個(gè)有窮狀態(tài)機(jī)包括下述5個(gè)部分：狀態(tài)集J、輸入集K、由當(dāng)前狀態(tài)和當(dāng)前輸入確定下一個(gè)狀態(tài)(次態(tài))的轉(zhuǎn)換函數(shù)T、初始態(tài)S和終態(tài)集F。對(duì)于保險(xiǎn)箱的例子，相應(yīng)的有窮狀態(tài)機(jī)的各部分如下。狀態(tài)集J：｛保險(xiǎn)箱鎖定，A，B，保險(xiǎn)箱解鎖，報(bào)警｝。輸入集K：｛1L，1R，2L，2R，3L，3R｝。圖4.1是一個(gè)有窮狀態(tài)機(jī)的狀態(tài)轉(zhuǎn)換圖。21轉(zhuǎn)換函數(shù)T：如表4.1所示。初始態(tài)S：保險(xiǎn)箱鎖定。終態(tài)集F：｛保險(xiǎn)箱解鎖，報(bào)警｝。一個(gè)有窮狀態(tài)機(jī)可以表示為一個(gè)5元組(J，K，T，S，F(xiàn))，其中：J是一個(gè)有窮的非空狀態(tài)集；K是一個(gè)有窮的非空輸入集；T是一個(gè)從(J-F)×K到J的轉(zhuǎn)換函數(shù)；?S∈J，是一個(gè)初始狀態(tài)；FJ，是終態(tài)集。轉(zhuǎn)換函數(shù)T：如表4.1所示。22一個(gè)保險(xiǎn)箱上裝了一個(gè)復(fù)合鎖，鎖有三個(gè)位置，分別標(biāo)記為1、2、3，轉(zhuǎn)盤可向左(L)或向右(R)轉(zhuǎn)動(dòng)。這樣，在任意時(shí)刻轉(zhuǎn)盤都有6種可能的運(yùn)動(dòng)，即1L、1R、2L、2R、3L和3R。保險(xiǎn)箱的組合密碼是1L、3R、2L，轉(zhuǎn)盤的任何其他運(yùn)動(dòng)都將引起報(bào)警，請(qǐng)畫出相應(yīng)狀態(tài)轉(zhuǎn)換圖。思考題一個(gè)保險(xiǎn)箱上裝了一個(gè)復(fù)合鎖，鎖有三個(gè)位置，分別標(biāo)記為1、2、23有窮狀態(tài)機(jī)方法采用了一種簡(jiǎn)單的格式來描述規(guī)格說明：當(dāng)前狀態(tài)+事件+(謂詞)下個(gè)狀態(tài)這種形式的規(guī)格說明易于書寫、易于驗(yàn)證，而且可以比較容易地把它轉(zhuǎn)變成設(shè)計(jì)或程序代碼。事實(shí)上，可以開發(fā)一個(gè)CASE工具把一個(gè)有窮狀態(tài)機(jī)規(guī)格說明直接轉(zhuǎn)變?yōu)樵创a。4.2.3評(píng)價(jià)有窮狀態(tài)機(jī)方法采用了一種簡(jiǎn)單的格式來描述規(guī)格說明：4.2.324有限自動(dòng)機(jī)有限自動(dòng)機(jī)（FA）是更一般化的狀態(tài)轉(zhuǎn)換圖，它分為確定有限自動(dòng)機(jī)DFA和非確定有限自動(dòng)機(jī)NFA兩種。

1．確定有限自動(dòng)機(jī)（DFA）一個(gè)確定的有限自動(dòng)機(jī)Md（記為DFAMd）是一個(gè)五元組Md=（S,Σ,f,s0,Z），其中：

(1)S是一個(gè)有限狀態(tài)集，它的每一個(gè)元素稱為一個(gè)狀態(tài)；

(2)Σ是一個(gè)有窮輸入字母表，它的每一個(gè)元素稱為一個(gè)輸入字符；有限自動(dòng)機(jī)25

(3)f是一個(gè)從S×Σ到S的單值映射即

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

(4)s0∈S，是惟一的一個(gè)初態(tài)；

(5)ZS，是一個(gè)終態(tài)集。例如，對(duì)下圖所給出的狀態(tài)s1有：

f(s1,a)=s2f(s1,b)=s3f(s1,c)=s4因此，f是單值映射函數(shù)。(3)f是一個(gè)從S×Σ到S的單值26圖DFA的狀態(tài)轉(zhuǎn)換示意圖DFA的狀態(tài)轉(zhuǎn)換示意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的狀態(tài)圖表示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的狀態(tài)圖表示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字符狀態(tài)DFA的矩陣表示f（S，a）=U f（V，a）=U字符狀302．非確定有限自動(dòng)機(jī)(NFA)

一個(gè)非確定有限自動(dòng)機(jī)Mn(記為NFAMn)

是一個(gè)五元組Mn=(S,Σ,f,s0,Z)，其中：

(1)S是一個(gè)有限狀態(tài)集，它的每一個(gè)元素稱為一個(gè)狀態(tài)；

(2)Σ是一個(gè)有窮輸入字母表，它的每一個(gè)元素稱為一個(gè)輸入字符；

(3)f是一個(gè)從S×Σ到S的子集映射；

(4)s0∈S，是惟一的一個(gè)初態(tài)；

(5)ZS，是一個(gè)終態(tài)集。

2．非確定有限自動(dòng)機(jī)(NFA)31

NFA和DFA的區(qū)別主要是：NFA的狀態(tài)轉(zhuǎn)換函數(shù)f不是單值函數(shù)，而是一個(gè)多值函數(shù)，即f(si，a)={某些狀態(tài)的集合}（si∈S），它表示不能由當(dāng)前狀態(tài)和當(dāng)前輸入字符惟一地確定下一個(gè)要轉(zhuǎn)換的狀態(tài)，也即允許同一個(gè)狀態(tài)對(duì)同一個(gè)輸入字符可以有不同的輸出邊。NFA和DFA的區(qū)別主要是：NFA的32圖NFA的狀態(tài)轉(zhuǎn)換示意圖NFA的狀態(tài)轉(zhuǎn)換示意33例如，對(duì)上圖所給出的狀態(tài)s1有：

f(s1,

a)={s1,s2,s3}

即f是一個(gè)從S×Σ*到S的子集映射；Σ*表示輸出邊上所標(biāo)記的不僅是字符，也可以是字。此外，NFA還允許f(s1,ε)={某些狀態(tài)的集合}，即在NFA的狀態(tài)轉(zhuǎn)換圖中輸出邊上的標(biāo)記還可是ε(空字)。例如，對(duì)上圖所給出的狀態(tài)s1有：343．狀態(tài)轉(zhuǎn)換圖與狀態(tài)轉(zhuǎn)換矩陣

(1)DFA和NFA都可以用狀態(tài)轉(zhuǎn)換圖表示。假定DFA（或NFA）有m個(gè)狀態(tài)、n個(gè)輸入字符（或字），則這個(gè)狀態(tài)轉(zhuǎn)換圖含有m個(gè)狀態(tài)，每個(gè)狀態(tài)最多有n條輸出邊與其它狀態(tài)相連接，每一條輸出邊用Σ（或Σ*）中的一個(gè)不