有限狀態(tài)機(jī)及其擴(kuò)展

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

2、規(guī)格、驗(yàn)證方法的基礎(chǔ)模型。 超級(jí)商場(chǎng)的自動(dòng)門(mén)控制器超級(jí)商場(chǎng)的自動(dòng)門(mén)控制器 自動(dòng)門(mén)的前、后分別有兩個(gè)緩沖自動(dòng)門(mén)的前、后分別有兩個(gè)緩沖 區(qū)。自動(dòng)門(mén)的前緩沖區(qū)用來(lái)檢測(cè)是否有人接近。自動(dòng)門(mén)的區(qū)。自動(dòng)門(mén)的前緩沖區(qū)用來(lái)檢測(cè)是否有人接近。自動(dòng)門(mén)的 后緩沖區(qū)，使得控制器把門(mén)打開(kāi)足夠長(zhǎng)的時(shí)間讓人走進(jìn)去，后緩沖區(qū)，使得控制器把門(mén)打開(kāi)足夠長(zhǎng)的時(shí)間讓人走進(jìn)去， 并且不讓門(mén)在打開(kāi)的時(shí)候碰到站在它附近的人。自動(dòng)門(mén)控并且不讓門(mén)在打開(kāi)的時(shí)候碰到站在它附近的人。自動(dòng)門(mén)控 制器依據(jù)前緩沖區(qū)、后緩沖區(qū)的檢測(cè)信息給出打開(kāi)或閉合制器依據(jù)前緩沖區(qū)、后緩沖區(qū)的檢測(cè)信息給出打開(kāi)或閉合 的動(dòng)作指令。的動(dòng)作指令。 自動(dòng)門(mén)的動(dòng)作控制應(yīng)滿足如下要求

3、（規(guī)格）：自動(dòng)門(mén)的動(dòng)作控制應(yīng)滿足如下要求（規(guī)格）： 當(dāng)前緩沖區(qū)和后緩沖區(qū)均無(wú)顧客出現(xiàn)，則自動(dòng)門(mén)處于閉當(dāng)前緩沖區(qū)和后緩沖區(qū)均無(wú)顧客出現(xiàn)，則自動(dòng)門(mén)處于閉 合狀態(tài)；合狀態(tài)； 當(dāng)后緩沖區(qū)有顧客出現(xiàn)，則自動(dòng)門(mén)維持其原有狀態(tài)；當(dāng)后緩沖區(qū)有顧客出現(xiàn)，則自動(dòng)門(mén)維持其原有狀態(tài)； 當(dāng)前緩沖區(qū)有顧客且后緩沖區(qū)無(wú)顧客，則打開(kāi)自動(dòng)門(mén)。當(dāng)前緩沖區(qū)有顧客且后緩沖區(qū)無(wú)顧客，則打開(kāi)自動(dòng)門(mén)。 前 緩 沖 區(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)系

4、集合狀態(tài)轉(zhuǎn)移關(guān)系集合 (closed, rear) =closed；(closed,both)=closed； (closed, neither)=closed；(closed,front)=open； (open, rear) = open； (open,both) =open； (open, front) = open；(open, neither) = closed closed：閉合狀態(tài)； open：打開(kāi)狀態(tài)；front：前緩沖區(qū)有顧客；rear：后緩沖區(qū)有顧客； both = front rear：前、后緩沖區(qū)都有顧客； neither = front rear：前、后緩沖區(qū)都無(wú)顧客

5、 closed open front neither both,rear,neitherboth,rear,front 前 緩 沖 區(qū) 后 緩 沖 區(qū) 4 （1） 基本概念基本概念 模模3計(jì)數(shù)器計(jì)數(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 0 1 dec 2 inc inc inc decdec inc：增加1 dec：減少1 5 （1） 基本概念基本概念 身份認(rèn)

6、證系統(tǒng)身份認(rèn)證系統(tǒng) （合法身份：（合法身份：ABAABA） 狀態(tài)集合狀態(tài)集合Q = 1, 2, 3, 4 ； 初始狀態(tài)初始狀態(tài) q0 = 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 (1,AB)=3 1 2 A 3 B,C B,C C B A 4 A 終結(jié)狀態(tài) accepting state 6 （1） 基本概念基本概念 有限狀態(tài)機(jī)是一個(gè)五

7、元組 M = (Q, , , q0, F)，其中 Q = q0, q1, qn是有限狀態(tài)集合。在任一確定的時(shí) 刻，有限狀態(tài)機(jī)只能處于一個(gè)確定的狀態(tài)qi； = 1,2, m是有限輸入字符集合。在任一確定 的時(shí)刻，有限狀態(tài)機(jī)只能接收一個(gè)確定的輸入j； ：Q Q是狀態(tài)轉(zhuǎn)移函數(shù)。如果在某一確定的時(shí) 刻，有限狀態(tài)機(jī)處于某一狀態(tài)qiQ，并接收一個(gè)輸入字 符j，那么下一時(shí)刻將處于一個(gè)確定的狀態(tài)q = (qi， j)Q。在這里規(guī)定q = (q，) ； q0 Q是初始狀態(tài)，有限狀態(tài)機(jī)由此狀態(tài)開(kāi)始接收輸入； F Q是終結(jié)狀態(tài)集合，有限狀態(tài)機(jī)在達(dá)到終結(jié)態(tài)后不 再接收輸入。 7 （1） 基本概念基本概念 ：字母表 字

8、符串：字母表上的字符組成的有限序列（為空串） 語(yǔ)言：字母表上的字符串的集合 當(dāng)=a,b，aabb,ab,abab,bba,等都是上的語(yǔ)言 有限狀態(tài)機(jī)接受的語(yǔ)言：L(M)=x|(q0,x) F 有限狀態(tài)機(jī)可用四元組 M = (Q, , , q0)或三元組 M = (Q, , )來(lái)表示。 狀態(tài)轉(zhuǎn)移函數(shù):刻畫(huà)其行為的最關(guān)鍵部分, 一個(gè)從Q到Q 的二元函數(shù)。狀態(tài)轉(zhuǎn)移函數(shù)通?？梢杂藐P(guān)系矩陣、狀 態(tài)轉(zhuǎn)移表或狀態(tài)轉(zhuǎn)移圖的形式來(lái)表示。 8 （1） 基本概念基本概念 o 狀態(tài)轉(zhuǎn)移矩陣 用行表示狀態(tài)機(jī)所處的當(dāng)前狀 態(tài)，列表示將要到達(dá)的下一個(gè)狀態(tài)，行列交叉 處表示輸入字符。稱該矩陣為轉(zhuǎn)移函數(shù)的關(guān) 系矩陣，或者有限狀

9、態(tài)機(jī)M的狀態(tài)轉(zhuǎn)移矩陣。 模3計(jì)數(shù)器 0 1 2 0 inc dec 2 inc dec 1 dec inc 狀態(tài)轉(zhuǎn)移矩陣 0 1 dec 2 inc inc inc decdec 9 o 狀態(tài)轉(zhuǎn)移表 用表格的行表示狀態(tài)機(jī)所處的當(dāng) 前狀態(tài)，列表示當(dāng)前的輸入字符，行列交叉處 表示要到達(dá)的下一個(gè)狀態(tài)。 模3計(jì)數(shù)器 輸入字符 狀態(tài) inc dec 1 2 0 1 2 0 0 1 2 狀態(tài)轉(zhuǎn)移表 0 1 dec 2 inc inc inc decdec 10 o 狀態(tài)轉(zhuǎn)移圖 用圓圈（結(jié)點(diǎn)）表示狀態(tài)；將存 在轉(zhuǎn)移關(guān)系的狀態(tài)用有向弧連接，并標(biāo)注相應(yīng) 的輸入字符在有向弧旁；用標(biāo)有箭頭的結(jié)點(diǎn)表 示初始狀態(tài)；屬于

10、終結(jié)狀態(tài)集中的狀態(tài)用雙圈 表示。 0 1 dec 2 inc inc inc dec dec 狀態(tài)轉(zhuǎn)移圖 模3計(jì)數(shù)器 11 （1） 基本概念基本概念 p 前面討論的有限狀態(tài)機(jī)，可以看作僅接受輸入符 號(hào)并發(fā)生狀態(tài)改變，但無(wú)任何輸出的自動(dòng)機(jī)器。 p 現(xiàn)實(shí)生活中的許多有限狀態(tài)系統(tǒng),對(duì)于不同的輸入 信號(hào)，除內(nèi)部狀態(tài)不斷改變外，還不斷向系統(tǒng)外 部輸出各種信號(hào)。 p 將有限狀態(tài)機(jī)進(jìn)行推廣，引出具有輸出機(jī)制的自 動(dòng)機(jī)器模型。 p 帶輸出的自動(dòng)機(jī)器模型，按照輸出的不同分成兩 類：輸出與狀態(tài)有關(guān)Moore機(jī)機(jī)；輸出與狀態(tài)和 輸入有關(guān)Mealy機(jī)機(jī)。 12 （2） Moore機(jī)機(jī) Moore機(jī)形式定義為六元組M

11、= (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 0 1 01 0 q0 q2 q1 例例：二進(jìn)制數(shù)的：二進(jìn)制數(shù)的 模模3余數(shù)余數(shù) Q = q0，q1，q2 S= 0，1 = 0,1,2 (qj) = j, j = 0,1,2 在輸入010100 下，輸出為012212 13 （2） Mealy機(jī)機(jī) Mealy機(jī)形式定義為六元組M = (Q, , , , , q0)，其中 Q = q0,q1,qn是有限狀態(tài)集合；

12、 = 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。 在輸入01100 下，輸出為nnyny 1/y0/n 1/n 0/y 0/n 1/n q0 q2 q1 14 （2） M

13、ealy機(jī)機(jī) 身份認(rèn)證系統(tǒng)（具有條件和變量機(jī)制的有限狀態(tài)機(jī)） (最大允許錯(cuò)誤次數(shù)為3)（err：報(bào)警狀態(tài)； ctr：計(jì)數(shù)變量） Xcon/Yexec含義在于：所標(biāo)注的狀態(tài)轉(zhuǎn)移關(guān)系在輸入x且條件con成立下，轉(zhuǎn)移至下一狀態(tài)， 并輸出y且執(zhí)行exec。標(biāo)注中的各項(xiàng)x、con、y或exec可以缺省。 12 A 3 B,Cctr3/ctr:=ctr+1 B A 4 err Cctr3/ctr:=ctr+1 B,Cctr=3/ctr:=ctr+1 B,Cctr=3/ctr:=ctr+1 A,Cctr=3/ctr:=ctr+1 B,Cctr3/ctr:=ctr+1 Actr3/ctr:=ctr+1 /ct

14、r:= 0 15 （2） Mealy機(jī)機(jī) 身份認(rèn)證系統(tǒng)身份認(rèn)證系統(tǒng) err 1 2 A3BA 4 ctr= 2 ctr= 2 ctr= 2 ctr= 2 1 2 A3BA 4 ctr= 3 ctr= 3 ctr= 3 ctr= 3 1 2 A3BA 4 ctr= 1 ctr= 1 ctr= 1 ctr= 1 1 2 A 3BA 4 ctr= 0 ctr= 0 ctr= 0 ctr= 0 ctr= 4 B,C B,C B,C B,C B,CB,C B,C B,C A,C C C C A A A 16 （3） 有限狀態(tài)機(jī)的復(fù)合有限狀態(tài)機(jī)的復(fù)合 o 通常，軟件系統(tǒng)是以模塊或子系統(tǒng)的形式出 現(xiàn) o 整

15、個(gè)軟件系統(tǒng)的有限狀態(tài)機(jī)規(guī)格,需要對(duì)各 個(gè)模塊的有限狀態(tài)機(jī)進(jìn)行復(fù)合。 o 有限狀態(tài)機(jī)復(fù)合的最簡(jiǎn)單方式是笛卡爾積 o 有限狀態(tài)機(jī)的笛卡爾積復(fù)合,規(guī)格了多個(gè)有 限狀態(tài)機(jī)相互獨(dú)立運(yùn)行的行為。 o 軟件系統(tǒng)之間存在交互問(wèn)題，有限狀態(tài)機(jī)的 復(fù)合也必然涉及交互問(wèn)題。 17 （3） 有限狀態(tài)機(jī)的復(fù)合有限狀態(tài)機(jī)的復(fù)合 有限狀態(tài)機(jī)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) = (q

16、1, q2) 1(q1, a1)=q1，a2 = ，a11 (q1, q2) 2(q2, a2)=q2，a1 = ，a22 (q1, q2) 1(q1, a1)=q1，2(q2, a2)=q2，a11， a22 無(wú)定義無(wú)定義 其余其余 18 （3） 有限狀態(tài)機(jī)的復(fù)合有限狀態(tài)機(jī)的復(fù)合 0 1 dec 2 inc inc inc decdec 模模3計(jì)數(shù)器計(jì)數(shù)器 模模4計(jì)數(shù)器計(jì)數(shù)器 0 1 dec 2 inc inc dec 3 inc inc dec dec dec o 模3和模4計(jì)數(shù)器的笛卡爾積復(fù)合有34=12 個(gè)狀態(tài) o 每個(gè)狀態(tài)下，兩個(gè)模計(jì)數(shù)器均可相互獨(dú)立地進(jìn) 行加數(shù)、減數(shù)或保持不變 19

17、 （3） 有限狀態(tài)機(jī)的復(fù)合有限狀態(tài)機(jī)的復(fù)合 o 每個(gè)狀態(tài)有33=9種狀態(tài)轉(zhuǎn)移選擇，但其中一種 為無(wú)任何狀態(tài)轉(zhuǎn)移發(fā)生，故只有8種狀態(tài)轉(zhuǎn)移。 o 其笛卡爾積復(fù)合具有128=96個(gè)狀態(tài)轉(zhuǎn)移 2,0 2,1 2,32,2 1,0 1,1 1,31,2 0,0 0,1 0,30,2 dec,dec inc, inc,dec inc,inc dec,incdec, ,inc ,dec 模計(jì)數(shù)器的笛卡爾積模計(jì)數(shù)器的笛卡爾積復(fù)合復(fù)合 20 有限狀態(tài)機(jī)的同步積復(fù)合有限狀態(tài)機(jī)的同步積復(fù)合 有限狀態(tài)機(jī)M1 = (Q1, 1, 1, q10)和M2 = (Q2, 2, 2, q20) 的同 步積復(fù)合為M = M1 M

18、2 = (Q, , , q0)，其中， Q = Q1Q2； = 1 2 ； q0 = (q10, q20) Q1Q2； (q1, q2), 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 無(wú)定義 其余 21 有限狀態(tài)機(jī)的同步積復(fù)合有限狀態(tài)機(jī)的同步積復(fù)合 模計(jì)數(shù)器的同步積模計(jì)數(shù)器的同步積復(fù)合復(fù)合 2,0 2,1 2,32,2 1,0 1,1 1,31,2 0,0 0,1 0,30,2 dec inc p模模3 3和模和模4 4計(jì)數(shù)器，可以進(jìn)行耦合運(yùn)行

19、，阻止各自的獨(dú)計(jì)數(shù)器，可以進(jìn)行耦合運(yùn)行，阻止各自的獨(dú) 立運(yùn)行行為。立運(yùn)行行為。 只有只有incinc、incinc和和decdec、decdec兩種共兩種共2424個(gè)狀態(tài)轉(zhuǎn)移個(gè)狀態(tài)轉(zhuǎn)移 22 有限狀態(tài)機(jī)的異步積復(fù)合有限狀態(tài)機(jī)的異步積復(fù)合 有限狀態(tài)機(jī)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)=q

20、1，a1 無(wú)定義 其余 23 有限狀態(tài)機(jī)的異步積復(fù)合有限狀態(tài)機(jī)的異步積復(fù)合 模計(jì)數(shù)器的異步積模計(jì)數(shù)器的異步積復(fù)合復(fù)合 2,0 2,1 2,32,2 1,0 1,1 1,31,2 0,0 0,1 0,30,2 inc dec inc dec p模模3 3和模和模4 4計(jì)數(shù)器，可以進(jìn)行耦合運(yùn)行，但在任何狀態(tài)計(jì)數(shù)器，可以進(jìn)行耦合運(yùn)行，但在任何狀態(tài) 下僅有其中一個(gè)模計(jì)數(shù)器運(yùn)行。下僅有其中一個(gè)模計(jì)數(shù)器運(yùn)行。 分別有分別有incinc和和decdec兩種共兩種共4848個(gè)狀態(tài)轉(zhuǎn)移個(gè)狀態(tài)轉(zhuǎn)移 （4 4） 生產(chǎn)者生產(chǎn)者- -消費(fèi)者問(wèn)題消費(fèi)者問(wèn)題 生產(chǎn)者消費(fèi)者系統(tǒng)生產(chǎn)者消費(fèi)者系統(tǒng)包含一個(gè)生產(chǎn)者和一個(gè)消費(fèi)者。生產(chǎn)

21、者進(jìn)程產(chǎn)包含一個(gè)生產(chǎn)者和一個(gè)消費(fèi)者。生產(chǎn)者進(jìn)程產(chǎn) 生消息，并把產(chǎn)生的消息寫(xiě)入一個(gè)能容納兩個(gè)消息的緩存區(qū)中。生消息，并把產(chǎn)生的消息寫(xiě)入一個(gè)能容納兩個(gè)消息的緩存區(qū)中。 生產(chǎn)者在進(jìn)行“生產(chǎn)”動(dòng)作后，狀態(tài)由P1轉(zhuǎn)變?yōu)镻2；而 在“寫(xiě)”動(dòng)作后，狀態(tài)由P2恢復(fù)為P1。消費(fèi)者進(jìn)程能讀 取消息，并把消息從緩存器中取走。消費(fèi)者在“讀”動(dòng) 作后，狀態(tài)由C1轉(zhuǎn)變?yōu)镃2；而在進(jìn)行“消費(fèi)”動(dòng)作后， 狀態(tài)由C2恢復(fù)為C1。如果緩存器是滿的，那么生產(chǎn)者進(jìn)如果緩存器是滿的，那么生產(chǎn)者進(jìn) 程必須等待，直到消費(fèi)者進(jìn)程從緩存器中取出一個(gè)消息，程必須等待，直到消費(fèi)者進(jìn)程從緩存器中取出一個(gè)消息， 使緩存器產(chǎn)生一個(gè)消息空位。同樣，如果緩

22、存器是空的，使緩存器產(chǎn)生一個(gè)消息空位。同樣，如果緩存器是空的， 那么消費(fèi)者進(jìn)程就必須等待，直到生產(chǎn)者進(jìn)程產(chǎn)生一個(gè)那么消費(fèi)者進(jìn)程就必須等待，直到生產(chǎn)者進(jìn)程產(chǎn)生一個(gè) 消息并把所產(chǎn)生的消息寫(xiě)入緩存器中。消息并把所產(chǎn)生的消息寫(xiě)入緩存器中。緩存器在進(jìn)行 “讀”動(dòng)作后，緩存器大小減“1”，而在“寫(xiě)”動(dòng)作后， 緩存器大小加“1”。 生產(chǎn)者生產(chǎn)者 P1 生產(chǎn) P2 寫(xiě) C1 讀 C2 消費(fèi)讀 20 讀 1 寫(xiě) 寫(xiě) 緩存器緩存器消費(fèi)者消費(fèi)者 25 （4 4） 生產(chǎn)者生產(chǎn)者- -消費(fèi)者問(wèn)題消費(fèi)者問(wèn)題 三個(gè)有限狀態(tài)機(jī) M1 = (P1, P2, 寫(xiě), 生產(chǎn), 1, P1) 、M2 = (C1, C2, 讀, 消費(fèi),

23、 2, C1) 、 M3 = (0, 1, 2, 讀, 寫(xiě), 3, 0)，顯然，1 3 讀，2 3 寫(xiě)。 三個(gè)有限狀態(tài)機(jī)的同步積復(fù)合M = M1 M2 M3，其中， Q = Q1Q2Q3； = 1 23； q0 = (q10, q20, q30) Q1Q2Q3； (q1, 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

24、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 (q1, q2, q3 ) 3(q3, a,)=q3，a 3，a 1，a 2 無(wú)定義 其余 （4 4） 生產(chǎn)者生產(chǎn)者- -消費(fèi)者問(wèn)題消費(fèi)者問(wèn)題 寫(xiě) 生產(chǎn) 讀 0, P1,C1 消費(fèi) 1, P1,C1 0, P1,C2 2, P1,C1 2, P1,C2 1, P1,C2 消費(fèi) 消費(fèi)讀 讀 0, P2,C1 消費(fèi) 1, P2,C1

25、 0, P2,C2 2, P2,C1 2, P2,C2 1, P2,C2 消費(fèi) 消費(fèi)讀 生產(chǎn) 生產(chǎn)生產(chǎn) 生產(chǎn)生產(chǎn) 寫(xiě) 寫(xiě) 寫(xiě) 生產(chǎn)者生產(chǎn)者 P1 生產(chǎn) P2 寫(xiě) C1 讀 C2 消費(fèi)讀 20 讀 1 寫(xiě)寫(xiě) 緩存器緩存器消費(fèi)者消費(fèi)者 27 有限狀態(tài)機(jī)的缺陷 u 在多有限狀態(tài)機(jī)系統(tǒng)中，系統(tǒng)的狀態(tài)為所有狀態(tài)機(jī)的狀態(tài)的 笛卡兒（同步、異步）積，因此系統(tǒng)的狀態(tài)數(shù)具有狀態(tài)組合 復(fù)雜性問(wèn)題。即使對(duì)于非常簡(jiǎn)單的情況，復(fù)合后系統(tǒng)的狀態(tài) 圖的規(guī)模也會(huì)變得非常龐大，甚至無(wú)法進(jìn)行； u 有限狀態(tài)機(jī)模型實(shí)質(zhì)上存在一個(gè)限制性假定：在系統(tǒng)所處的 每一個(gè)狀態(tài)上，在任何時(shí)刻，最多執(zhí)行一個(gè)操作。因此，有 限狀態(tài)機(jī)主要描述順序系統(tǒng)

26、，并發(fā)描述能力很弱； u 有限狀態(tài)機(jī)不能描述無(wú)限狀態(tài)系統(tǒng)，同時(shí)，缺乏描述時(shí)間特 性的機(jī)制。有限狀態(tài)機(jī)也不適合于描述系統(tǒng)的功能和結(jié)構(gòu)特 性。 28 （二）（二） Statecharts （1） StatechartsStatecharts中的狀態(tài)中的狀態(tài) Statecharts是由以色列的Harel于1987年建立的傳統(tǒng)有限狀態(tài)機(jī)的一 種擴(kuò)展形式。Statecharts中通過(guò)引入狀態(tài)的遞階（層次化）、狀態(tài) 的“與（AND）”分解和“或（OR）”分解等高級(jí)特性，從而具有了 更強(qiáng)的描述能力。Statecharts中狀態(tài)用圓角方框圖示，狀態(tài)名標(biāo)注 在圓角方框內(nèi)的上方 。 S S2 S22S21S1 S

27、1 F F S3 S2 T1 T S U T2 29 狀態(tài)的層次化狀態(tài)的層次化 有限狀態(tài)機(jī)在輸入F下均可從狀態(tài)S或T轉(zhuǎn)移到狀態(tài)U。這里可將 狀態(tài)S和T合并成一個(gè)新的狀態(tài)，記為狀態(tài)V，并將兩個(gè)狀態(tài)轉(zhuǎn)移 弧用一個(gè)弧來(lái)代替。狀態(tài)的層次化通過(guò)框圖的嵌套來(lái)圖示。 具有子狀態(tài)的狀態(tài)稱為遞階狀態(tài)，沒(méi)有子狀態(tài)的狀態(tài)稱為簡(jiǎn)單 狀態(tài)或者原子狀態(tài)。 高級(jí)狀態(tài)或超狀態(tài)、父狀態(tài)、先輩狀態(tài)、子狀態(tài)、后代狀態(tài) （任意深度多層次描述） S F F U T S V F U T S S2 S22S21S1 30 或（或（OR）狀態(tài)、與（）狀態(tài)、與（AND）狀態(tài)）狀態(tài) u狀態(tài)的層次化可以通過(guò)自頂向下的狀態(tài)分解，或自底向上的狀態(tài)合并

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

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

30、和動(dòng)作以觸發(fā)和動(dòng)作以“事件事件 條條 件件/動(dòng)作動(dòng)作”的形式標(biāo)注在遷移弧旁。的形式標(biāo)注在遷移弧旁。 S1 Ein(S1)/R t=2/F S3 S2 T1 T S R T2 RF /E F/R 32 遷移上的條件、事件和動(dòng)作遷移上的條件、事件和動(dòng)作 預(yù)定義的與狀態(tài)、數(shù)據(jù)項(xiàng)、時(shí)間有關(guān)的條件、事件和動(dòng)作 （P36） 條件：in(S) 表示是否處于狀態(tài)S中，如是則為真，否則為假； ac(A) 表示活動(dòng)A是否處于活動(dòng)狀態(tài)，如是則為真，否則為假； hg(A) 表示活動(dòng)A是否處于掛起狀態(tài)，如是則為真，否則為假； 事件：en(S) 表示進(jìn)入狀態(tài)S；ex(S) 表示退出狀態(tài)S； ns表示正在進(jìn)入當(dāng)前狀態(tài)； x

31、s表示正在退出當(dāng)前狀態(tài)； st(A)表示活動(dòng)A被啟動(dòng)；st表示當(dāng)前活動(dòng)被啟動(dòng)；sp(A)表示活動(dòng)A被停止； tr(C)表示條件C變?yōu)檎?；fs(C)表示條件C變?yōu)榧伲?rd(X)表示X被動(dòng)作rd!讀；wr(X)表示X被動(dòng)作wr!寫(xiě)；ch(X)表示數(shù)據(jù)項(xiàng)X的值發(fā)生改變； tm(E，N)表示事件E發(fā)生后，已過(guò)了N個(gè)時(shí)間單位。 動(dòng)作：tr!(C) 表示對(duì)條件C賦值真；fs!(C) 表示對(duì)條件C賦值假； st!(A)表示啟動(dòng)活動(dòng)A；sp!(A)表示停止活動(dòng)A；sd!(A)表示掛起活動(dòng)A； rs!(A)表示重新開(kāi)始活動(dòng)A； rd!(X) 表示讀數(shù)據(jù)或條件X；wr!(X) 表示寫(xiě)數(shù)據(jù)或條件X； 事件、條件和

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

33、則相當(dāng)于指向其所有的子狀態(tài)；，則相當(dāng)于指向其所有的子狀態(tài)；當(dāng)遷移指向當(dāng)遷移指向 一個(gè)或狀態(tài)時(shí)一個(gè)或狀態(tài)時(shí)，則相當(dāng)于指向其缺省的子狀態(tài)。當(dāng)退出一個(gè)狀態(tài)時(shí)，則相當(dāng)于指向其缺省的子狀態(tài)。當(dāng)退出一個(gè)狀態(tài)時(shí)， 則相當(dāng)退出其所有的子狀態(tài)則相當(dāng)退出其所有的子狀態(tài)。 R F S2 S22S21 S1 R F S2 S22S21 S1 U R F S S22S21 S1 T T2T1 U 34 復(fù)合遷移復(fù)合遷移 o為了簡(jiǎn)化圖形中遷移的有向弧線，Statecharts中引 入了一些輔助符號(hào)，從而得到狀態(tài)之間轉(zhuǎn)移關(guān)系的復(fù) 合遷移。 o條件連接符 也稱為C-連接符，用于條件的連接。 Statecharts規(guī)定始于C-

34、連接符的條件分支可以多個(gè)， 但是這些條件分支必須是異或的。 S1 S3 S2 C1 E C C2 S1 S3 S2 EC1 EC2 35 復(fù)合遷移復(fù)合遷移 -開(kāi)關(guān)連接符 開(kāi)關(guān)連接符，也稱為S-連接符，用于事件的連接。 S1 S3 S2 E1 A S E2 E3 S1 S3 S2 AE1 AE2 AE3 36 復(fù)合遷移復(fù)合遷移-分叉（匯合）連接符 遷移的觸發(fā)和（或）動(dòng)作的相同部分，可以通過(guò)分叉 （匯合）連接符形成一個(gè)單一的弧線進(jìn)入（離開(kāi)） 連接符。 分叉（匯合）連接符適用于條件連接符和開(kāi)關(guān)連接符 所不能描述的情形。 S1 S3 S2 R /A S S1 S3 S2 C1 E F S1 S3 S2

35、 SET S1 S3 S2 /A C1 E 37 復(fù)合遷移復(fù)合遷移 -分叉（匯合）結(jié)構(gòu) o分叉（匯合）結(jié)構(gòu)是進(jìn)入（離開(kāi)）與狀態(tài)的子狀態(tài)遷 移的一種描述方式。 o此類結(jié)構(gòu)下復(fù)合遷移所聯(lián)系的狀態(tài)轉(zhuǎn)移，要求遷移上 所有的觸發(fā)同時(shí)滿足，且動(dòng)作也都同時(shí)執(zhí)行。 U S1 S3 S S2 S4 A E1/A1 c2/A2 U S1 S3 S S2 S4 A c1/A1 E2/A2 38 復(fù)合遷移復(fù)合遷移 -圖形連接符 o圖形連接符可以實(shí)現(xiàn)遷移的異地連接圖形連接符可以實(shí)現(xiàn)遷移的異地連接。用橢圓符號(hào)并標(biāo) 注相同的名稱來(lái)圖示。 oStatecharts規(guī)定每個(gè)圖形連接符出現(xiàn)與所連接的遷移必須 具有相同方向的弧線（

36、離開(kāi)或者進(jìn)入）。 S1INT S S2 S3 A E1/A1 INT R INT 39 復(fù)合遷移復(fù)合遷移 -歷史連接符 o歷史連接符規(guī)定系統(tǒng)進(jìn)入一個(gè)狀態(tài)組中的一個(gè)最近訪問(wèn)歷史連接符規(guī)定系統(tǒng)進(jìn)入一個(gè)狀態(tài)組中的一個(gè)最近訪問(wèn) 歷史狀態(tài)歷史狀態(tài),用標(biāo)注H的圓圈圖示。 o歷史連接符可以理解為一個(gè)特殊的狀態(tài)。進(jìn)入歷史連接 符就表示進(jìn)入該連接符所在狀態(tài)組中最近訪問(wèn)的那個(gè)狀 態(tài)，若歷史狀態(tài)為空，則進(jìn)入歷史連接符所指向的狀態(tài)。 S1 H S2 T S 從狀態(tài)從狀態(tài)T進(jìn)入狀態(tài)進(jìn)入狀態(tài)S時(shí)，首先進(jìn)入其歷史時(shí)，首先進(jìn)入其歷史 狀態(tài)狀態(tài)H，即進(jìn)入最近訪問(wèn)的那個(gè)狀態(tài)。，即進(jìn)入最近訪問(wèn)的那個(gè)狀態(tài)。 若上次訪問(wèn)的狀態(tài)為若上次

37、訪問(wèn)的狀態(tài)為S2，則進(jìn)入狀態(tài)，則進(jìn)入狀態(tài)S2。 如果如果H為空，則進(jìn)入為空，則進(jìn)入S1狀態(tài)。狀態(tài)。 交通燈控制系統(tǒng)交通燈控制系統(tǒng) 40 41 電梯運(yùn)動(dòng)系統(tǒng) o 某個(gè)樓層 j 所能觀察到的電梯運(yùn)動(dòng)有如下可 能的幾種情形： o電梯一直向上移動(dòng)； o電梯一直向下移動(dòng)； o電梯從下面往上逐漸靠近，停止，然后繼續(xù)向上運(yùn)動(dòng)； o電梯從上面往下逐漸靠近，停止，然后繼續(xù)向下運(yùn)動(dòng)； o電梯從下面往上逐漸靠近，停止，然后反向向下運(yùn)動(dòng)； o電梯從上面往下逐漸靠近，停止，然后反向向上運(yùn)動(dòng)； o電梯從下面往上逐漸靠近，停止，然后在空閑狀態(tài)等待； o電梯從上面往下逐漸靠近，停止，然后在空閑狀態(tài)等待； o從空閑狀態(tài)起動(dòng)，然

38、后向下運(yùn)動(dòng)； 從空閑狀態(tài)起動(dòng)，然后向上運(yùn)動(dòng)。 電梯運(yùn)動(dòng)系統(tǒng) 對(duì)于某樓層j的觀察者，電梯可能會(huì)處于如下?tīng)顟B(tài)之一： o等待(w:wait)：在該層等待，并且門(mén)未打開(kāi)； o停止-空閑(s-i:stop-idle)：停在該層，并且門(mén)打開(kāi)； o停止-向上(s-u:stop-up)：電梯在向上運(yùn)動(dòng)過(guò)程中在該樓層暫停； o停止-向下(s-d:stop-down)：電梯在向下運(yùn)動(dòng)過(guò)程中在該樓層暫停； o靠近-向上(a-u:approach-up)：電梯在向上運(yùn)動(dòng)過(guò)程中逐漸靠近該樓層； o靠近-向下(a-d:approach-down)：電梯在向下運(yùn)動(dòng)過(guò)程中逐漸靠近該樓層； o退出-向上(e-u:exit-up

39、)：電梯離開(kāi)該樓層，繼續(xù)向上運(yùn)動(dòng)； 退出-向下(e-d:exit-down)：電梯離開(kāi)該樓層，繼續(xù)向下運(yùn)動(dòng)。 e-u e-u e-d e-d a-u s-u e-u e-d s-d a-d e-ua-d s-us-d a-u s-u e-d s-d a-u s-u w s-i a-d s-d w s-i e-u s-u w e-d s-d w 電梯運(yùn)動(dòng)系統(tǒng)電梯運(yùn)動(dòng)系統(tǒng)StatechartsStatecharts規(guī)格規(guī)格 exit exit-downexit-up stop stop-upstop-down stop-idle call close-door close-door reduce-speedwait approach approach-up approach-down 狀態(tài)s-u、s-d和s-i可以合并為 一個(gè)超狀態(tài)超狀態(tài)stop；狀態(tài)a-u和a-d 合并為超狀態(tài)超狀態(tài)approach；狀態(tài) e-u和e-d合并為超狀態(tài)超狀態(tài)exit。 電梯經(jīng)過(guò)在某樓層的暫停后， 將合上門(mén)然后離開(kāi)該樓層，這 一過(guò)程規(guī)格為狀態(tài)狀態(tài)stop在觸發(fā)在觸發(fā) 事件事件close-door下轉(zhuǎn)移到狀態(tài)下轉(zhuǎn)移到狀態(tài) exit。 當(dāng)存在某樓層