【文章內(nèi)容簡介】 對。 所謂關(guān)聯(lián)比較是指對那些在順序比較時尚未確定是否等效的狀態(tài)對作進(jìn)一步檢查。 關(guān)聯(lián)比較時，首先要確定隱含表中待檢查的那些次態(tài)對是否等效，并由此確定原狀態(tài)對是否等效。如果隱含表中某方格內(nèi)有一個次態(tài)對不等效，則該方格所對應(yīng)的兩個狀態(tài)就不等效，于是在相應(yīng)方格中增加標(biāo)志“／”。若方格內(nèi)的次態(tài)對均為等效狀態(tài)對，則與該方格對應(yīng)的狀態(tài)為等效狀態(tài)，該方格不增加任何標(biāo)志。這種判別有時要反復(fù)多次，直到判別出狀態(tài)對等效或不等效為止。 ③求出最大等效類。在找出原始狀態(tài)表中的所有等效對之后，可利用等效狀態(tài)的傳遞性，求出各最大等效類。確定各最大等效類時應(yīng)注意兩點(diǎn)：一是各最大等效類之間不應(yīng)出現(xiàn)相同狀態(tài)，因為若兩個等效類之間有相同狀態(tài)，則根據(jù)等效的傳遞性可令其合為一個等效類；二是原始狀態(tài)表中的每一個狀態(tài)都必須屬于某一個最大等效類，換句話說， 各最大等效類所包含的狀態(tài)之和必須覆蓋原始狀態(tài)表中的全部狀態(tài)，否則，化簡后的狀態(tài)表不能描述原始狀態(tài)表所描述的功能。 ?下面舉例說明化簡過程。 例 . 化簡所示原始狀態(tài)表。 解 該表為具有 7個狀態(tài)的原始狀態(tài)表。用隱含表法化簡如下。 ①作隱含表。根據(jù)畫隱含表的規(guī)則，可得到與給定狀態(tài)表對應(yīng)的隱含表框架如圖所示。由于原始狀態(tài)表中有 AG共 7個狀態(tài)，所以隱含表的橫向和縱向各有 6個方格?？v向從上到下依次為 BG， 橫向從左到右依次為 A~F。 表中每個方格代表一個狀態(tài)對，如左上角的方格代表狀態(tài)對 A和 B， 右下角的方格代表狀態(tài)對 F和 G。 B C D E F G A B C D E F 隱含表格式 ④作出最小化狀態(tài)表。根據(jù)求出的最大等效類，將每個最大等效類中的全部狀態(tài)合并為一個狀態(tài)，即可得到和原始狀態(tài)表等價的最小化狀態(tài)表。 ②尋找等效對。首先進(jìn)行順序比較，根據(jù)等效狀態(tài)的判斷標(biāo)準(zhǔn)，依次檢查每個狀態(tài)對，可得到順序比較結(jié)果如下圖所示。 例如，狀態(tài)表中 C和 F滿足狀態(tài)等效條件，所以，在隱含表的相應(yīng)方格內(nèi)填入“ √”；狀態(tài) A和 C不滿足等效條件，故在隱含表的相應(yīng)方格內(nèi)填入“”；狀態(tài) A和 E雖然滿足輸出相同這個條件，但它們的次態(tài)在 x=1時為 B和 E， 由于當(dāng)前尚不能確定 B和 E是否等效，因此，將 BE填人相應(yīng)方格中。 輸入 狀態(tài) X=0 X=1 A C/0 B/1 B F/0 A/1 C F/0 G/0 D D/1 E/0 E C/0 E/1 F C/0 G/0 G C/1 D/0 B CF C D E BE AECF F √ G CDDE A B C D E F 根據(jù)輸出 ,7個狀態(tài)分成 3組： {C， F} {A， B， E} {D， G} 組內(nèi)狀態(tài)才有可能等效。 –經(jīng)過順序比較后，還有 A和 B， A和 E， B和 E以及 D和 C共 4個狀態(tài)對尚未確定是否等效。故應(yīng)接著進(jìn)行關(guān)聯(lián)比較，其結(jié)果如右圖所示。 例如，在圖中，狀態(tài) A、 B對應(yīng)的方格中次態(tài)對為 CF， 而狀態(tài) C、F對應(yīng)的方格標(biāo)有“ √”號，表明狀態(tài) C和 F等效，由此可判斷出狀態(tài) A和 B等效。 檢查狀態(tài) A、 E的次態(tài)對，出現(xiàn)如下循環(huán)關(guān)系： 已知狀態(tài) C和 F是等效的，而狀態(tài) BE又與狀態(tài) AB構(gòu)成循環(huán)，所以，狀態(tài) A和 E是等效狀態(tài)對， B和 E也是等效狀態(tài)對。 B CF C D E BE AECF F √ G CDDE A B C D E F AE→BE→CF ↑ B CF C D E BE AECF F √ G CDDE A B C D E F 狀態(tài) D、 G對應(yīng)的方格中含有 CD和 DE， 而狀態(tài) C、D對應(yīng)的方格已標(biāo)以“ X”號，這表明狀態(tài) C和 D不等效。因此，可以判斷狀態(tài) D和 G不等效，它所對應(yīng)的方格應(yīng)增加記號“／”。 由隱含表可知，原始狀態(tài)表中的 7個狀態(tài)共有四個等效對： (A， B)， (A， E)， (B， E)， (C， F)。 ③ 求出最大等效類。由所得到的四個等效對可知，等效對 (A， B)， (A， E)， (B， E)構(gòu)成一個最大等效類｛ A， B， E}。 等效對 (C， F)不包含在任何其他等效類中，所以，它也是一個最大等效類。其次，狀態(tài) D和 G不和任何其他狀態(tài)等效，故它們各自構(gòu)成一個最大等效類。由此可見，原始狀態(tài)表中的 7個狀態(tài)共構(gòu)成四個最大等效類，分別表示如下： {A， B， E}， {C， F}， {D}，{G}。 ④作出最小化狀態(tài)表。將最大等效類 {A， B， E}、 {C，F(xiàn)}、 {D}、 {G}分別用新的字母 a、 b、 c、 d表示，并代入原表狀態(tài)表中，即可得到化簡后的最小化狀態(tài)表如下表所示。 輸入 狀態(tài) X=0 X=1 a b/0 a/1 b b/0 d/0 c c/1 a/0 d b/1 c/0 不完全確定狀態(tài)表的化簡 ? 在討論形成原始狀態(tài)表時已經(jīng)看到，根據(jù)實(shí)際問題所形成的原始狀態(tài)表除完全確定狀態(tài)表之外，還存在另一類不完全確定狀態(tài)表。在這類狀態(tài)表中存在不確定的次態(tài)或輸出。無疑，這些不確定的狀態(tài)和輸出對于狀態(tài)化簡將是有利的，關(guān)鍵是必須適當(dāng)處理，以確保化簡前后狀態(tài)表的邏輯功能不變。為此，提出了一個新的概念 —— 相容狀態(tài)。不完全確定狀態(tài)表的化簡是建立在相容狀態(tài)基礎(chǔ)上的。 (1)相容狀態(tài)和相容類 ①相容狀態(tài)。假定狀態(tài) Si和 Sj是不完全確定狀態(tài)表中的兩個狀態(tài)，如果對于所有的有效輸入序列，分別從狀態(tài) Si和 Sj出發(fā)，所得到的輸出響應(yīng)序列 (除不確定的那些位之外 )是完全相同的，那么，狀態(tài) Si和 Sj是相容的，或者說狀態(tài) Si和 Sj是相容對，記作 (Si， Sj)。 從狀態(tài)表中的狀態(tài) S出發(fā)，如果給定某輸入序列所得到的狀態(tài)響應(yīng)序列除最后一個次態(tài)外，其他次態(tài)都是確定的，那么這個輸入序列對狀態(tài) S是有效的。所有的有效輸入序列，是指有效輸入序列的長度和結(jié)構(gòu)是任意的。 ?在不完全確定狀態(tài)表中，判斷兩個狀態(tài)是否相容的依據(jù)是表中給出的次態(tài)和輸出。假定狀態(tài) Si和 Sj是不完全確定狀態(tài)表中的兩個現(xiàn)態(tài)，那么，狀態(tài) Si和 Sj相容的條件，可歸納為在一位輸入的各種取值組合下滿足如下兩條。 第一，它們的輸出完全相同，或者其中的一個 (或兩個 )輸出不 確定。 第二，它們的次態(tài)屬于下列情況之一： a． 次態(tài)相同； b． 次態(tài)交錯或為各自的現(xiàn)態(tài)； c． 次態(tài)循環(huán)或為相容對； d． 其中的一個 (或兩個 )為不確定狀態(tài)。 必須指出， 相容狀態(tài)不具有傳遞性。 即不能由 S1和 S2相容、S2和 S3相容，推出 S1和 S3也相容。這是因為判斷兩個狀態(tài)是否相容時，對于不給定的輸出和不給定的次態(tài)可以隨意指定的緣故。 ②相容類。相容類是由彼此相容的狀態(tài)構(gòu)成的集合。處于同一相容類中的所有狀態(tài)之間都是兩兩相容的。例如，若有相容對 (S1， S2)、 (S2，S3)和 (S1， S3)， 則可構(gòu)成相容類 {S1， S2， S3}。 ③ 最大相容類。若一個相容類不是任何其他相容類的子集，則該相容類稱為最大相容類。由于相容狀態(tài)無傳遞性，所以，同一原始狀態(tài)表的各最大相容類之間可能存在相同狀態(tài)，即同一狀態(tài)可能出現(xiàn)在不同的最大相容類中。 (2)不完全確定狀態(tài)表的化簡 不完全確定狀態(tài)表的化簡過程與完全確定狀態(tài)表的化簡過程相似，只是在某些環(huán)節(jié)的具體處理上稍有不同。其一般步驟與方法如下。 ? ① 作隱含表，尋找相容狀態(tài)對。利用隱含表尋找相容對的過程與化簡完全確定狀態(tài)表時尋找等效對的過程是相同的，僅僅是狀態(tài)相容與狀態(tài)等效的標(biāo)準(zhǔn)有所不同而已。即畫好隱含表后，首先依次判別每個狀態(tài)對的相容關(guān)系，并將判斷結(jié)果標(biāo)注到隱含表中。若某個狀態(tài)對相容，則在相應(yīng)方格中填入“ √”；若某個狀態(tài)對是不相容的，則在相應(yīng)方格中填入“”；若兩個狀態(tài)的輸出相同 (或者不確定 )，而其次態(tài)尚不能直接確定是否相容，則在相應(yīng)方格中填入與之相關(guān)的次態(tài)對。 在順序比較完成后，可利用已建立的隱含表繼續(xù)追蹤待確定的狀態(tài)，即進(jìn)行關(guān)聯(lián)比較。如果與之關(guān)聯(lián)的次態(tài)對都是相容的，則原狀態(tài)對是相容的；只要某方格中填入的次態(tài)對中有一對不相容，則該方格所對應(yīng)的狀態(tài)對不相容，在該方格中填人標(biāo)記“／”。逐個檢查，直至判斷出所有狀態(tài)對相容或不相容為止，即可列出原始狀態(tài)表中的全部相容對。 ? ②利用狀態(tài)合并圖，求出最大相容類。為了方便地找到最大相容類，可以借助于狀態(tài)合并圖。狀態(tài)合并圖是一種將不完全確定狀態(tài)表的狀態(tài)，以“點(diǎn)”的形式均勻地繪在圓周上，然后把所有相容對都用線段連接起來而得到的圖。在這種圖中，圓周上的點(diǎn)表示狀態(tài)，點(diǎn)與點(diǎn)之間的連線表示兩狀態(tài)之間的相容關(guān)系， 所有頂點(diǎn)之