第2章 有限狀態(tài)機及其擴展

1、1Chapter 2 有限狀態(tài)機及其擴展有限狀態(tài)機及其擴展 o有限狀態(tài)機有限狀態(tài)機 n 有限狀態(tài)機是有限計算的基本模型，也是許多形式化規(guī)格、驗證方法的基礎(chǔ)模型。o Statecharts n Statecharts是通過定義遞階狀態(tài)、狀態(tài)的AND或OR分解等高級特性的有限狀態(tài)機的一種擴展形式。2（一）（一） 有限狀態(tài)機有限狀態(tài)機（1） 基本概念基本概念 有限狀態(tài)機（有限狀態(tài)機（finite state machine）或有限自動機）或有限自動機（finite automata）是有限計算的基本模型，是許多形式化）是有限計算的基本模型，是許多形式化規(guī)格、驗證方法的基礎(chǔ)模型。規(guī)格、驗證方法的基礎(chǔ)模

2、型。 超級商場的自動門控制器超級商場的自動門控制器 自動門的前、后分別有兩個緩沖自動門的前、后分別有兩個緩沖區(qū)。自動門的前緩沖區(qū)用來檢測是否有人接近。自動門的區(qū)。自動門的前緩沖區(qū)用來檢測是否有人接近。自動門的后緩沖區(qū)，使得控制器把門打開足夠長的時間讓人走進去，后緩沖區(qū)，使得控制器把門打開足夠長的時間讓人走進去，并且不讓門在打開的時候碰到站在它附近的人。自動門控并且不讓門在打開的時候碰到站在它附近的人。自動門控制器依據(jù)前緩沖區(qū)、后緩沖區(qū)的檢測信息給出打開或閉合制器依據(jù)前緩沖區(qū)、后緩沖區(qū)的檢測信息給出打開或閉合的動作指令。的動作指令。 自動門的動作控制應(yīng)滿足如下要求（規(guī)格）：自動門的動作控制應(yīng)滿足

3、如下要求（規(guī)格）： 當前緩沖區(qū)和后緩沖區(qū)均無顧客出現(xiàn)，則自動門處于閉當前緩沖區(qū)和后緩沖區(qū)均無顧客出現(xiàn)，則自動門處于閉合狀態(tài)；合狀態(tài)； 當后緩沖區(qū)有顧客出現(xiàn)，則自動門維持其原有狀態(tài)；當后緩沖區(qū)有顧客出現(xiàn)，則自動門維持其原有狀態(tài)； 當前緩沖區(qū)有顧客且后緩沖區(qū)無顧客，則打開自動門。當前緩沖區(qū)有顧客且后緩沖區(qū)無顧客，則打開自動門。前緩沖區(qū)后緩沖區(qū)（1） 基本概念基本概念狀態(tài)集合狀態(tài)集合Q = closed, open；初始狀態(tài)初始狀態(tài) q0 = closed；輸入集合輸入集合 = front, rear, both, neither狀態(tài)轉(zhuǎn)移關(guān)系集合狀態(tài)轉(zhuǎn)移關(guān)系集合 (closed, rear) =cl

4、osed；(closed,both)=closed；(closed, neither)=closed；(closed,front)=open(open, rear) = pen； (open,both) =open； (open, front) = open；(open, neither) = closedclosed：閉合狀態(tài)； open：打開狀態(tài)；front：前緩沖區(qū)有顧客；rear：后緩沖區(qū)有顧客；both = front rear：前、后緩沖區(qū)都有顧客；neither = front rear：前、后緩沖區(qū)都無顧客closed openfrontneitherboth,rear,nei

5、therboth,rear,front前緩沖區(qū)后緩沖區(qū)4（1） 基本概念基本概念模模3計數(shù)器計數(shù)器 狀態(tài)集合狀態(tài)集合Q = 0, 1, 2 ；初始狀態(tài)初始狀態(tài) q0 = 0；輸入集合輸入集合 = inc, dec狀態(tài)轉(zhuǎn)移關(guān)系集合狀態(tài)轉(zhuǎn)移關(guān)系集合(0,inc)=1；(0,dec)=2；(1,inc)=2；(1,dec)=0；(2,inc)=0；(2,dec)=1 01dec2incincincdecdecinc：增加1dec：減少15（1） 基本概念基本概念身份認證系統(tǒng)身份認證系統(tǒng) （合法身份：（合法身份：ABAABA） 狀態(tài)集合狀態(tài)集合Q = 1, 2, 3, 4 ； 初始狀態(tài)初始狀態(tài) q0

6、= 1； 終結(jié)狀態(tài)集合終結(jié)狀態(tài)集合 F = 4； 輸入集合輸入集合 = A, B, C 狀態(tài)轉(zhuǎn)移關(guān)系集合狀態(tài)轉(zhuǎn)移關(guān)系集合 (1,A)=2；(1,B)=1；(1,C) =1；(2,A)=2；(2,B)=3；(2,C) =1；(3,A) =4；(3,B)=1；(3,C) =1 ABCACA AABCABA 12A3B,CB,CCBA4A6（1） 基本概念基本概念有限狀態(tài)機是一個五元組 M = (Q, , , q0, F)，其中 Q = q0, q1, qn是有限狀態(tài)集合。在任一確定的時刻，有限狀態(tài)機只能處于一個確定的狀態(tài)qi； = 1,2, m是有限輸入字符集合。在任一確定的時刻，有限狀態(tài)機只能接

7、收一個確定的輸入j； ：Q Q是狀態(tài)轉(zhuǎn)移函數(shù)。如果在某一確定的時刻，有限狀態(tài)機處于某一狀態(tài)qiQ，并接收一個輸入字符j，那么下一時刻將處于一個確定的狀態(tài)q = (qi，j)Q。在這里規(guī)定q = (q，) ； q0 Q是初始狀態(tài)，有限狀態(tài)機由此狀態(tài)開始接收輸入； F Q是終結(jié)狀態(tài)集合，有限狀態(tài)機在達到終結(jié)態(tài)后不再接收輸入。 7（1） 基本概念基本概念一個有限狀態(tài)機包括：一個有限狀態(tài)集，用于描述系統(tǒng)中的不同狀態(tài)；一個輸入符號集，用于表征系統(tǒng)所接收的不同輸入信息；一個狀態(tài)轉(zhuǎn)移函數(shù)，用于表述系統(tǒng)在接收不同輸入下,從一個狀態(tài)轉(zhuǎn)移到另外一個狀態(tài)的規(guī)則。 狀態(tài)轉(zhuǎn)移函數(shù):刻畫其行為的最關(guān)鍵部分, 一個從Q到Q

8、的二元函數(shù)。狀態(tài)轉(zhuǎn)移函數(shù)通?？梢杂藐P(guān)系矩陣、狀態(tài)轉(zhuǎn)移表或狀態(tài)轉(zhuǎn)移圖的形式來表示。有限狀態(tài)機可用四元組 M = (Q, , , q0)或三元組 M = (Q, , )來表示。8（1） 基本概念基本概念o 狀態(tài)轉(zhuǎn)移矩陣 用行表示狀態(tài)機所處的當前狀態(tài)，列表示將要到達的下一個狀態(tài)，行列交叉處表示輸入字符。稱該矩陣為轉(zhuǎn)移函數(shù)的關(guān)系矩陣，或者有限狀態(tài)機M 的狀態(tài)轉(zhuǎn)移矩陣。模3計數(shù)器 0 1 20 inc dec2 inc dec1 dec inc狀態(tài)轉(zhuǎn)移矩陣9o 狀態(tài)轉(zhuǎn)移表 用表格的行表示狀態(tài)機所處的當前狀態(tài)，列表示當前的輸入字符，行列交叉處表示要到達的下一個狀態(tài)。稱該表格為M的狀態(tài)轉(zhuǎn)換表。模3計數(shù)器 輸

9、入字符狀態(tài)inc dec1 20 12 0 012狀態(tài)轉(zhuǎn)移表10o 狀態(tài)轉(zhuǎn)移圖 用圓圈（結(jié)點）表示狀態(tài)；將存在轉(zhuǎn)移關(guān)系的狀態(tài)用有向弧連接，并標注相應(yīng)的輸入字符在有向弧旁；用標有箭頭的結(jié)點表示初始狀態(tài)；屬于終結(jié)狀態(tài)集中的狀態(tài)用雙圈表示。 01dec2incincincdecdec狀態(tài)轉(zhuǎn)移圖模3計數(shù)器 11（1） 基本概念基本概念p 前面討論的有限狀態(tài)機，可以看作僅接受輸入符號并發(fā)生狀態(tài)改變，但無任何輸出的自動機器。p 現(xiàn)實生活中的許多有限狀態(tài)系統(tǒng),對于不同的輸入信號，除內(nèi)部狀態(tài)不斷改變外，還不斷向系統(tǒng)外部輸出各種信號。p 將有限狀態(tài)機進行推廣，引出具有輸出機制的自動機器模型。p 帶輸出的自動機器

10、模型，按照輸出的不同分成兩類：輸出與狀態(tài)有關(guān)Moore機機；輸出與狀態(tài)和輸入有關(guān)Mealy機機。 12（1） 基本概念基本概念Moore機形式定義為六元組M = (Q, , , , , q0)，其中 Q = q0,q1,qn是有限狀態(tài)集合； = 1,2,m是有限輸入字符集合； = a1,a2,ar是有限輸出字符集合； ：Q Q是狀態(tài)轉(zhuǎn)移函數(shù)； ：Q 是輸出函數(shù)； q0 Q是初始狀態(tài)。 1/10/01/20/11/00/2q0q2q1例例：模：模3余數(shù)余數(shù)Q = q0，q1，q2= 0，1(qj) = j, j = 0,1,2在輸入010100 下，輸出為012212 13（1） 基本概念基本概

11、念Mealy機形式定義為六元組M = (Q, , , , , q0)，其中 Q = q0,q1,qn是有限狀態(tài)集合； = 1,2,m是有限輸入字符集合； = a1,a2,ar是有限輸出字符集合； ：Q Q是狀態(tài)轉(zhuǎn)移函數(shù)； ：Q 是輸出函數(shù)； q0 Q 是初始狀態(tài)。 狀態(tài)轉(zhuǎn)移函數(shù)為：(q0,0) = q1, (q0,1) = q2, (q1,1) = q2, (q1,0) = q1, (q2,1) = q2, (q2,0) = q1輸出函數(shù)為： (q0,0) = n, (q0,1) = n, (q1,1) = n, (q1,0) = y, (q2,1) = y, (q2,0) = n。在輸入01

12、100 下，輸出為nnyny 1/y0/n1/n0/y0/n1/nq0q2q114（1） 基本概念基本概念身份認證系統(tǒng)（具有條件和變量機制的有限狀態(tài)機）(最大允許錯誤次數(shù)為3)（err：報警狀態(tài)； ctr：計數(shù)變量）Xcon/Yexec含義在于：所標注的狀態(tài)轉(zhuǎn)移關(guān)系在輸入x且條件con成立下，轉(zhuǎn)移至下一狀態(tài)，并輸出y且執(zhí)行exec。標注中的各項x、con、y或exec可以缺省。12A3B,Cctr3/ctr:=ctr+1 BA4errCctr3/ctr:=ctr+1 B,Cctr=3/ctr:=ctr+1 B,Cctr=3/ctr:=ctr+1 A,Cctr=3/ctr:=ctr+1 B,Cc

13、tr3/ctr:=ctr+1 Actr3/ctr:=ctr+1 /ctr:= 0 15（1） 基本概念基本概念身份認證系統(tǒng)身份認證系統(tǒng)err12A3BA4ctr= 2 ctr= 2 ctr= 2 ctr= 2 12A3BA4ctr= 3 ctr= 3 ctr= 3 ctr= 3 12A3BA4ctr= 1 ctr= 1 ctr= 1 ctr= 1 12A3BA4ctr= 0 ctr= 0 ctr= 0 ctr= 0 ctr= 4 B,CB,CB,CB,CB,CB,CB,CB,CA,CCCCAAA16（2） 有限狀態(tài)機的復(fù)合有限狀態(tài)機的復(fù)合o 通常，軟件系統(tǒng)是以模塊或子系統(tǒng)的形式出現(xiàn)o 整個軟件

14、系統(tǒng)的有限狀態(tài)機規(guī)格,需要對各個模塊的有限狀態(tài)機進行復(fù)合。o 有限狀態(tài)機復(fù)合的最簡單方式是笛卡爾積o 有限狀態(tài)機的笛卡爾積復(fù)合,規(guī)格了多個有限狀態(tài)機相互獨立運行的行為。o 軟件系統(tǒng)之間存在交互問題，有限狀態(tài)機的復(fù)合也必然涉及交互問題。17（2） 有限狀態(tài)機的復(fù)合有限狀態(tài)機的復(fù)合有限狀態(tài)機M1 = (Q1, 1, 1, q10)和M2 = (Q2, 2, 2, q20) 的笛卡爾積為M = M1 M2 = (Q, , , q0)，其中， Q = Q1Q2； = (1 )(2 )； q0 = (q10, q20) Q1Q2； (q1, q2), (a1, a2) = (q1, q2) 1(q1,

15、a1)=q1，a2 = ，a11 (q1, q2) 2(q2, a2)=q2，a1 = ，a22 (q1, q2) 1(q1, a1)=q1，2(q2, a2)=q2，a11，a22 無定義無定義 其余其余 18（2） 有限狀態(tài)機的復(fù)合有限狀態(tài)機的復(fù)合01dec2incincincdecdec模模3計數(shù)器計數(shù)器模模4計數(shù)器計數(shù)器01dec2incincdec3incincdecdecdeco 模3和模4計數(shù)器的笛卡爾積復(fù)合有34=12個狀態(tài)o 每個狀態(tài)下，兩個模計數(shù)器均可相互獨立地進行加數(shù)、減數(shù)或保持不變19（2） 有限狀態(tài)機的復(fù)合有限狀態(tài)機的復(fù)合o 每個狀態(tài)有33=9種狀態(tài)轉(zhuǎn)移選擇，但其中一

16、種為無任何狀態(tài)轉(zhuǎn)移發(fā)生，故只有8種狀態(tài)轉(zhuǎn)移。o 其笛卡爾積復(fù)合具有128=96個狀態(tài)轉(zhuǎn)移2,02,12,32,21,01,11,31,20,00,10,30,2dec,decinc,inc,decinc,incdec,incdec,inc,dec模計數(shù)器的笛卡爾積模計數(shù)器的笛卡爾積復(fù)合復(fù)合 20有限狀態(tài)機的同步積復(fù)合有限狀態(tài)機的同步積復(fù)合有限狀態(tài)機M1 = (Q1, 1, 1, q10)和M2 = (Q2, 2, 2, q20) 的同步積復(fù)合為M = M1 M2 = (Q, , , q0)，其中， Q = Q1Q2； = 1 2 ； q0 = (q10, q20) Q1Q2； (q1, q2)

17、, a) = (q1, q2) 1(q1, a)=q1， 2(q2, a)=q2，a1 2 (q1, q2) 2(q2, a)=q2，a1，a2 (q1, q2) 1(q1, a)=q1，a1，a2 無定義 其余 21有限狀態(tài)機的同步積復(fù)合有限狀態(tài)機的同步積復(fù)合模計數(shù)器的同步積模計數(shù)器的同步積復(fù)合復(fù)合 2,02,12,32,21,01,11,31,20,00,10,30,2decincp模模3 3和模和模4 4計數(shù)器，可以進行耦合運行，阻止各自的獨計數(shù)器，可以進行耦合運行，阻止各自的獨立運行行為。立運行行為。只有只有incinc、incinc和和decdec、decdec兩種共兩種共2424個

18、狀態(tài)轉(zhuǎn)移個狀態(tài)轉(zhuǎn)移22有限狀態(tài)機的異步積復(fù)合有限狀態(tài)機的異步積復(fù)合有限狀態(tài)機M1 = (Q1, 1, 1, q10)和M2 = (Q2, 2, 2, q20) 的異步積復(fù)合為M = M1 M2 = (Q, , , q0)，其中， Q = Q1Q2； = 1 2 ； q0 = (q10, q20) Q1Q2； (q1, q2), a) = (q1, q2) 2(q2, a)=q2，a2 (q1, q2) 1(q1, a)=q1，a1 無定義 其余23有限狀態(tài)機的異步積復(fù)合有限狀態(tài)機的異步積復(fù)合模計數(shù)器的異步積模計數(shù)器的異步積復(fù)合復(fù)合 2,02,12,32,21,01,11,31,20,00,10

19、,30,2incdecincdecp模模3 3和模和模4 4計數(shù)器，可以進行耦合運行，但在任何狀態(tài)計數(shù)器，可以進行耦合運行，但在任何狀態(tài)下僅有其中一個模計數(shù)器運行。下僅有其中一個模計數(shù)器運行。 分別有分別有incinc和和decdec兩種共兩種共4848個狀態(tài)轉(zhuǎn)移個狀態(tài)轉(zhuǎn)移（3 3） 生產(chǎn)者生產(chǎn)者- -消費者問題消費者問題 生產(chǎn)者消費者系統(tǒng)生產(chǎn)者消費者系統(tǒng)包含一個生產(chǎn)者和一個消費者。生產(chǎn)者進程產(chǎn)包含一個生產(chǎn)者和一個消費者。生產(chǎn)者進程產(chǎn)生消息，并把產(chǎn)生的消息寫入一個能容納兩個消息的緩存區(qū)中。生消息，并把產(chǎn)生的消息寫入一個能容納兩個消息的緩存區(qū)中。 生產(chǎn)者在進行“生產(chǎn)”動作后，狀態(tài)由P1轉(zhuǎn)變?yōu)镻2

20、；而在“寫”動作后，狀態(tài)由P2恢復(fù)為P1。消費者進程能讀取消息，并把消息從緩存器中取走。消費者在“讀”動作后，狀態(tài)由C1轉(zhuǎn)變?yōu)镃2；而在進行“消費”動作后，狀態(tài)由C2恢復(fù)為C1。如果緩存器是滿的，那么生產(chǎn)者進如果緩存器是滿的，那么生產(chǎn)者進程必須等待，直到消費者進程從緩存器中取出一個消息，程必須等待，直到消費者進程從緩存器中取出一個消息，使緩存器產(chǎn)生一個消息空位。同樣，如果緩存器是空的，使緩存器產(chǎn)生一個消息空位。同樣，如果緩存器是空的，那么消費者進程就必須等待，直到生產(chǎn)者進程產(chǎn)生一個那么消費者進程就必須等待，直到生產(chǎn)者進程產(chǎn)生一個消息并把所產(chǎn)生的消息寫入緩存器中。消息并把所產(chǎn)生的消息寫入緩存器中

21、。緩存器在進行“讀”動作后，緩存器大小減“1”，而在“寫”動作后，緩存器大小加“1”。 生產(chǎn)者生產(chǎn)者P1生產(chǎn)P2寫C1讀C2消費讀20讀1寫寫緩存器緩存器消費者消費者25（3 3） 生產(chǎn)者生產(chǎn)者- -消費者問題消費者問題 三個有限狀態(tài)機 M1 = (P1, P2, 寫, 生產(chǎn), 1, P1) 、M2 = (C1, C2, 讀, 消費, 2, C1) 、M3 = (0, 1, 2, 讀, 寫, 3, 0)，顯然，1 3 讀，2 3 寫。三個有限狀態(tài)機的同步積復(fù)合M = M1 M2 M3，其中， Q = Q1Q2Q3； = 1 23； q0 = (q10, q20, q30) Q1Q2Q3； (q

22、1, q2, q3), a) = (q1, q2, q3) 1(q1, a,)=q1，2(q2, a,)=q2，3(q3, a,)=q3，a 1 23 (q1, q2, q3) 1(q1, a,)=q1，2(q2, a,)=q2，a 1 2，a 3 (q1, q2, q3) 1(q1, a,)=q1，3(q3, a,)=q3，a 1 3，a 2 (q1, q2, q3) 2(q2, a,)=q2，3(q3, a,)=q3，a 2 3，a 1 (q1, q2, q3 ) 1(q1, a,)=q1，a 1，a 2，a 3 (q1, q2, q3 ) 2(q2, a,)=q2，a 2，a 1，a 3

23、 (q1, q2, q3 ) 3(q3, a,)=q3，a 3，a 1，a 2 無定義 其余（3 3） 生產(chǎn)者生產(chǎn)者- -消費者問題消費者問題寫生產(chǎn)讀0, P1,C1 消費1, P1,C1 0, P1,C2 2, P1,C1 2, P1,C2 1, P1,C2 消費消費讀讀0, P2,C1 消費1, P2,C1 0, P2,C2 2, P2,C1 2, P2,C2 1, P2,C2 消費消費讀生產(chǎn)生產(chǎn)生產(chǎn)生產(chǎn)生產(chǎn)寫寫寫生產(chǎn)者生產(chǎn)者P1生產(chǎn)P2寫C1讀C2消費讀20讀1寫寫緩存器緩存器消費者消費者27（3 3） 生產(chǎn)者生產(chǎn)者- -消費者問題消費者問題IIII ( (略）略）課堂練習：生產(chǎn)者消費者

24、系統(tǒng)II包含兩個生產(chǎn)者和一個消費者。生產(chǎn)者進程產(chǎn)生消息，并等待消費者消費。 生產(chǎn)者在進行“生產(chǎn)”動作后，狀態(tài)由P1轉(zhuǎn)變?yōu)镻2；而在“寫”動作后，狀態(tài)由P2恢復(fù)為P1。消費者進程能讀取消息，消費者在“讀”動作后，狀態(tài)由C1轉(zhuǎn)變?yōu)镃2；而在進行“消費”動作后，狀態(tài)由C2恢復(fù)為C1。生產(chǎn)者進程在產(chǎn)生一個消息后必須等待，直到消費者進程取出所產(chǎn)生的消息。同樣，如果沒有生產(chǎn)者進程產(chǎn)生的消息，那么消費者進程就必須等待，直到生產(chǎn)者進程產(chǎn)生一個消息。類似問題：生產(chǎn)者消費者系統(tǒng)包含兩個生產(chǎn)者、一個消費者和1個緩存容量的緩存單元？生產(chǎn)者消費者系統(tǒng)包含m個生產(chǎn)者、n個消費者和b個緩存容量的緩存單元？（3 3） 生產(chǎn)者

25、生產(chǎn)者- -消費者問題消費者問題IIII生產(chǎn)者生產(chǎn)者1P11生產(chǎn)1P12寫1C1讀C2消費消費者消費者生產(chǎn)者生產(chǎn)者2P21生產(chǎn)2P22寫2P11, P21,C1 P11, P22,C1P11, P21,C2P11, P22,C2消費消費P12, P21,C1消費P12, P22,C1P12, P21,C2P12, P22,C2消費生產(chǎn)1生產(chǎn)1生產(chǎn)2生產(chǎn)2生產(chǎn)1生產(chǎn)2生產(chǎn)1生產(chǎn)229有限狀態(tài)機的缺陷u 在多有限狀態(tài)機系統(tǒng)中，系統(tǒng)的狀態(tài)為所有狀態(tài)機的狀態(tài)的笛卡兒（同步、異步）積，因此系統(tǒng)的狀態(tài)數(shù)具有狀態(tài)組合復(fù)雜性問題。即使對于非常簡單的情況，復(fù)合后系統(tǒng)的狀態(tài)圖的規(guī)模也會變得非常龐大，甚至無法進行；

26、u 有限狀態(tài)機模型實質(zhì)上存在一個限制性假定：在系統(tǒng)所處的每一個狀態(tài)上，在任何時刻，最多執(zhí)行一個操作。因此，有限狀態(tài)機僅能夠描述順序系統(tǒng)，無并發(fā)描述的能力；u 有限狀態(tài)機不能描述無限狀態(tài)系統(tǒng)，同時，缺乏描述時間特性的機制。有限狀態(tài)機也不適合于描述系統(tǒng)的功能和結(jié)構(gòu)特性。 30（二）（二） Statecharts （1） StatechartsStatecharts中的狀態(tài)中的狀態(tài) Statecharts是由以色列的Harel于1987年建立的傳統(tǒng)有限狀態(tài)機的一種擴展形式。Statecharts中通過引入狀態(tài)的遞階（層次化）、狀態(tài)的“與（AND）”分解和“或（OR）”分解等高級特性，從而具有了更強的

27、描述能力。Statecharts中狀態(tài)用圓角方框圖示，狀態(tài)名標注在圓角方框內(nèi)的上方 。SS2S22S21S1S1FFS3S2T1TSUT231 狀態(tài)的層次化狀態(tài)的層次化 有限狀態(tài)機在輸入F下均可從狀態(tài)S或T轉(zhuǎn)移到狀態(tài)U。這里可將狀態(tài)S和T合并成一個新的狀態(tài)，記為狀態(tài)V，并將兩個狀態(tài)轉(zhuǎn)移弧用一個弧來代替。狀態(tài)的層次化通過框圖的嵌套來圖示。具有子狀態(tài)的狀態(tài)稱為遞階狀態(tài)，沒有子狀態(tài)的狀態(tài)稱為簡單狀態(tài)或者原子狀態(tài)。高級狀態(tài)或超狀態(tài)、父狀態(tài)、先輩狀態(tài)、子狀態(tài)、后代狀態(tài)（任意深度多層次描述）SFFUT SVFUTSS2S22S21S132 或（或（OR）狀態(tài)、與（）狀態(tài)、與（AND）狀態(tài)）狀態(tài)u狀態(tài)的層次

28、化可以通過自頂向下的狀態(tài)分解，或自底向上的狀態(tài)合并來實現(xiàn)。狀態(tài)的層次化可以通過自頂向下的狀態(tài)分解，或自底向上的狀態(tài)合并來實現(xiàn)。u或（或（OROR）狀態(tài)狀態(tài)：當且僅當位于該狀態(tài)就是位于其中的一個子狀態(tài)，即，位于一個或狀態(tài)不能同時位于該狀態(tài)的兩個以上的子狀態(tài)?；驙顟B(tài)表示了子狀態(tài)之間的一種異或關(guān)系。狀態(tài)的或狀態(tài)表示，稱為狀態(tài)的或分解。u與（與（ANDAND）狀態(tài)狀態(tài)：當且僅當位于該狀態(tài)就是同時位于其所有的子狀態(tài)。與狀態(tài)表示了子狀態(tài)之間的一種與關(guān)系。狀態(tài)的與狀態(tài)表示，稱為狀態(tài)的正交分解；與狀態(tài)的子狀態(tài)，又稱為狀態(tài)的正交分量。圖形表示中，用虛線將與狀態(tài)的正交分量或子狀態(tài)進行隔離，與狀態(tài)的標識符（即，狀態(tài)

29、名）標注在和狀態(tài)邊框連與狀態(tài)的標識符（即，狀態(tài)名）標注在和狀態(tài)邊框連在一體的小方框內(nèi)在一體的小方框內(nèi)。S1FFS3S2T1TSUT2SS2S22S21S133 （2 2） StatechartsStatecharts中的遷移中的遷移 遷移上的條件、事件和動作遷移的輸入遷移的輸入稱為觸發(fā)觸發(fā)（trigger），觸發(fā)可以是事件或者（和）條件。遷移的輸出遷移的輸出稱為動作動作（action），動作可以是產(chǎn)生新的事件或執(zhí)行一個過程或函數(shù)等。輸入是狀態(tài)之間遷移發(fā)生的原因，只有當一個遷移的輸入事件出現(xiàn)或者（和）遷移的輸入中條件滿足時，該遷移所聯(lián)系的狀態(tài)才可發(fā)生轉(zhuǎn)移。動作的執(zhí)行被認為是瞬時的。觸發(fā)和動作以觸

30、發(fā)和動作以“事件事件 條條件件/動作動作”的形式標注在遷移弧旁。的形式標注在遷移弧旁。 S1Ein(S1)/Rt=2/FS3S2T1TSRT2RF/EF/R34 遷移上的條件、事件和動作遷移上的條件、事件和動作預(yù)定義的與狀態(tài)、數(shù)據(jù)項、時間有關(guān)的條件、事件和動作 （P36） 條件：in(S) 表示是否處于狀態(tài)S中，如是則為真，否則為假； ac(A) 表示活動A是否處于活動狀態(tài)，如是則為真，否則為假； hg(A) 表示活動A是否處于掛起狀態(tài)，如是則為真，否則為假；事件：en(S) 表示進入狀態(tài)S；ex(S) 表示退出狀態(tài)S；ns表示正在進入當前狀態(tài)； xs表示正在退出當前狀態(tài)；st(A)表示活動A

31、被啟動；st表示當前活動被啟動；sp(A)表示活動A被停止；tr(C)表示條件C變?yōu)檎?；fs(C)表示條件C變?yōu)榧伲籸d(X)表示X被動作rd!讀；wr(X)表示X被動作wr!寫；ch(X)表示數(shù)據(jù)項X的值發(fā)生改變；tm(E，N)表示事件E發(fā)生后，已過了N個時間單位。動作：tr!(C) 表示對條件C賦值真；fs!(C) 表示對條件C賦值假；st!(A)表示啟動活動A；sp!(A)表示停止活動A；sd!(A)表示掛起活動A；rs!(A)表示重新開始活動A；rd!(X) 表示讀數(shù)據(jù)或條件X；wr!(X) 表示寫數(shù)據(jù)或條件X；hc!(S) 表示忘記狀態(tài)S的歷史信息；hd!(S) 表示忘記狀態(tài)S的后繼

32、狀態(tài)的歷史信息。事件、條件和動作可進行邏輯and ,or ,not等運算。如：E1 and E2表示事件E1與E2同時發(fā)生；C1 or C2表示C1和C2的或邏輯運算。 遷移與狀態(tài)的連接遷移與狀態(tài)的連接 遷移描述了簡單狀態(tài)和簡單狀態(tài)、簡單狀態(tài)和遞階狀態(tài)、遞階狀態(tài)和遞階狀態(tài)之間的狀態(tài)轉(zhuǎn)移關(guān)系。遷移用有向弧圖示，有向弧可以從一個狀態(tài)的邊界引出，終止于另一狀態(tài)的邊界，也可以穿過先輩狀態(tài)的邊界。當一個遷移沒有指明其源狀態(tài)時，則稱之為缺省遷移。其所指向的狀態(tài)，稱為缺省狀態(tài)。缺省遷移用圓點箭線弧表示。缺省遷移可以指向一個狀態(tài)，也可以穿過先輩狀態(tài)的邊框直接指向某一子狀態(tài)。當遷移指向一個與狀態(tài)時當遷移指向一個

33、與狀態(tài)時，則相當于指向其所有的子狀態(tài)；，則相當于指向其所有的子狀態(tài)；當遷移指向當遷移指向一個或狀態(tài)時一個或狀態(tài)時，則相當于指向其缺省的子狀態(tài)。當退出一個狀態(tài)時，則相當于指向其缺省的子狀態(tài)。當退出一個狀態(tài)時，則相當退出其所有的子狀態(tài)則相當退出其所有的子狀態(tài)。RFS2S22S21S1RFS2S22S21S1URFSS22S21S1TT2T1U36 復(fù)合遷移復(fù)合遷移 o為了簡化圖形中遷移的有向弧線，Statecharts中引入了一些輔助符號，從而得到狀態(tài)之間轉(zhuǎn)移關(guān)系的復(fù)合遷移。o條件連接符 也稱為C-連接符，用于條件的連接。Statecharts規(guī)定始于C-連接符的條件分支可以多個，但是這些條件分支

34、必須是異或的。 S1S3S2C1ECC2S1S3S2EC1EC237 復(fù)合遷移復(fù)合遷移 -開關(guān)連接符 開關(guān)連接符，也稱為S-連接符，用于事件的連接。 S1S3S2E1ASE2E3S1S3S2AE1AE2AE338 復(fù)合遷移復(fù)合遷移-分叉（匯合）連接符 遷移的觸發(fā)和（或）動作的相同部分，可以通過分叉（匯合）連接符形成一個單一的弧線進入（離開）連接符。分叉（匯合）連接符適用于條件連接符和開關(guān)連接符所不能描述的情形。 S1S3S2R/ASS1S3S2C1EFS1S3S2SETS1S3S2/AC1E等價 Statecharts圖？39 復(fù)合遷移復(fù)合遷移 -分叉（匯合）結(jié)構(gòu) o分叉（匯合）結(jié)構(gòu)是進入（離

35、開）與狀態(tài)的子狀態(tài)遷移的一種描述方式。o此類結(jié)構(gòu)下復(fù)合遷移所聯(lián)系的狀態(tài)轉(zhuǎn)移，要求遷移上所有的觸發(fā)同時滿足，且動作也都同時執(zhí)行。 US1S3SS2S4AE1/A1c2/A2US1S3SS2S4Ac1/A1E2/A240 復(fù)合遷移復(fù)合遷移 -圖形連接符 o圖形連接符可以實現(xiàn)遷移的異地連接圖形連接符可以實現(xiàn)遷移的異地連接。用橢圓符號并標注相同的名稱來圖示。oStatecharts規(guī)定每個圖形連接符出現(xiàn)與所連接的遷移必須具有相同方向的弧線（離開或者進入）。 S1INTSS2S3AE1/A1INTRINT41 復(fù)合遷移復(fù)合遷移 -歷史連接符 o歷史連接符規(guī)定系統(tǒng)進入一個狀態(tài)組中的一個最近訪問歷史連接符規(guī)

36、定系統(tǒng)進入一個狀態(tài)組中的一個最近訪問歷史狀態(tài)歷史狀態(tài),用標注H的圓圈圖示。o歷史連接符可以理解為一個特殊的狀態(tài)。進入歷史連接符就表示進入該連接符所在狀態(tài)組中最近訪問的那個狀態(tài)，若歷史狀態(tài)為空，則進入歷史連接符所指向的狀態(tài)。 S1HS2TS從狀態(tài)從狀態(tài)T進入狀態(tài)進入狀態(tài)S時，首先進入其歷史時，首先進入其歷史狀態(tài)狀態(tài)H，即進入最近訪問的那個狀態(tài)。，即進入最近訪問的那個狀態(tài)。若上次訪問的狀態(tài)為若上次訪問的狀態(tài)為S2，則進入狀態(tài)，則進入狀態(tài)S2。如果如果H為空，則進入為空，則進入S1狀態(tài)。狀態(tài)。 42 （3 3） 電梯控制系統(tǒng)電梯控制系統(tǒng)o考慮一個m層的大樓、n個電梯的服務(wù)系統(tǒng)。需要建立一個用以描述電

37、梯在樓層之間的運動,并完成電梯控制系統(tǒng)開發(fā)的規(guī)格，系統(tǒng)存在如下一些約束和要求：o 每個電梯內(nèi)部都有一組按鈕，每個按鈕用于指示一個樓層。當按下某個按鈕后，該按鈕指示燈就會發(fā)亮，直到到達相應(yīng)的樓層后按鈕的指示燈自動熄滅；43 電梯控制系統(tǒng)電梯控制系統(tǒng)o 除了最高層和最低層以外，每個樓層都有兩個按鈕：一個用于請求電梯向下移動，一個用于請求電梯向上移動。這些按鈕在被按下后，相應(yīng)指示燈就會發(fā)亮。當電梯按照所請求的方向移動離開該樓層時，按鈕的指示燈自動熄滅；o 在沒有服務(wù)請求時，電梯停留在其當前所處于的樓層，并且電梯門關(guān)閉。 o 整個電梯控制系統(tǒng)可分為：電梯控制按鈕、樓層控制按鈕和電梯運動系統(tǒng)三個部分。4

38、4 電梯控制按鈕o描述電梯按鈕、按鈕狀態(tài)以及狀態(tài)轉(zhuǎn)換的符號定義如描述電梯按鈕、按鈕狀態(tài)以及狀態(tài)轉(zhuǎn)換的符號定義如下下：oebij 電梯i中對應(yīng)于樓層j的按鈕；oebonij ebij的指示燈為亮的狀態(tài)狀態(tài)；oeboffij eb ij的指示燈為熄滅的狀態(tài)狀態(tài)；opress_ebij ebij被按下時所產(chǎn)生的事件事件；oarrives_atij 電梯i到達樓層j時所產(chǎn)生的事件事件。 ebonijeboffijarrives-atijpress-ebij45 樓層控制按鈕o除了最底層和最高層以外，其它各樓層都有兩個按鈕：一個用于一個用于請求電梯向上運動，另一個用于請求電梯向下運動請求電梯向上運動，另

39、一個用于請求電梯向下運動。用以描述的相應(yīng)符號為：ofbbj 樓層j對應(yīng)于運動方向b的按鈕（b up down）；ofbonbj fbbj的指示燈為亮的狀態(tài)；ofboffbj fbbj的指示燈為熄滅的狀態(tài)；ocall_fbbj 在fbbj被按下時所產(chǎn)生的事件；odepart_atbj 在方向b上運動的電梯離開樓層j時所產(chǎn)生的事件。 fbonbjfboffbjcall-fbbjdepart-atbj46 電梯運動系統(tǒng)o 某個樓層j所能觀察到的電梯運動有如下可能的幾種情形：電梯一直向上移動；電梯一直向下移動；電梯從下面往上逐漸靠近，停止，然后繼續(xù)向上運動；電梯從上面往下逐漸靠近，停止，然后繼續(xù)向下運

40、動；電梯從下面往上逐漸靠近，停止，然后反向向下運動；電梯從上面往下逐漸靠近，停止，然后反向向上運動；電梯從下面往上逐漸靠近，停止，然后在空閑狀態(tài)等待；電梯從上面往下逐漸靠近，停止，然后在空閑狀態(tài)等待；從空閑狀態(tài)起動，然后向下運動；從空閑狀態(tài)起動，然后向上運動。 電梯運動系統(tǒng)對于某樓層的觀察者，電梯可能會處于如下狀態(tài)之一：等待(w:wait)：在該層等待，并且門未打開；停止-空閑(s-i:stop-idle)：停在該層，并且門打開；停止-向上(s-u:stop-up)：電梯在向上運動過程中在該樓層暫停；停止-向下(s-d:stop-down)：電梯在向下運動過程中在該樓層暫停；靠近-向上(a-u

41、:approach-up)：電梯在向上運動過程中逐漸靠近該樓層；靠近-向下(a-d:approach-down)：電梯在向下運動過程中逐漸靠近該樓層；退出-向上(e-u:exit-up)：電梯離開該樓層，繼續(xù)向上運動；退出-向下(e-d:exit-down)：電梯離開該樓層，繼續(xù)向下運動。 e-ue-u e-de-d a-us-ue-ue-ds-da-d e-ua-d s-us-d a-us-ue-ds-d a-us-uws-i a-d s-dws-ie-u s-uwe-ds-dw 電梯運動系統(tǒng)電梯運動系統(tǒng)StatechartsStatecharts規(guī)格規(guī)格 sensorsensorexitexit-downexit-upstopstop-upstop-downstop-idlecall-fbbjclose-doorclose-doorreduce-speedwaitapproachapproach-upapproach-down狀態(tài)s-u、s-d和s-i可以合并