【正文】 ， D)、 (C， D)。而如果在滿足最小覆蓋的前提下，在最大相容類和非最大相容類之間作適當(dāng)?shù)倪x擇，卻能得到最簡的狀態(tài)表。 ? 例如，本例中選最大相容類 {A， B， D}、 {A， C， D}、{A， C， E}中的 {A， B， D}和相容類 {A， B}、 {A，C}、 {A， D}、 {A， E}、 {B， D}、 {C， D}、 {C， E}中的 {C， E}組成相容類集 { {A， B， D}， {C， E} }作為最小閉覆蓋，可得到相同的結(jié)果。例如，原始狀態(tài)表中的狀態(tài) A、B、 D在輸入 x=0時(shí)的輸出有 1和 d兩種，合并后的狀態(tài)a在 x=0時(shí)的輸出應(yīng)為 1。假定最小閉覆蓋中的相容類{A， B， D}用狀態(tài) a表示，相容類 {A， C， E}用狀態(tài) b表示，將其代入原始狀態(tài)表中，可得到下面所示的最小化狀態(tài)表。 B AC C AD D √ √ √ E √ AD BC A B C D 最大相容類 覆 蓋 閉 合 A B C D E X=0 X=1 ABD A B D AC B ACD A C D AD B ACE A C E AD C 由閉覆蓋表和選擇最小閉覆蓋的 3個(gè)條件 (覆蓋、閉合、最小 )可知，本例的最小閉覆蓋可由最大相容類 {A， B， D}和 {A， C，E}組成。 ③ 作閉覆蓋表，求最小閉覆蓋。 根據(jù)相容狀態(tài)對可作出狀態(tài)合并圖。 輸入 狀態(tài) X=0 X=1 A A/d d/d B C/1 B/0 C D/0 d/1 D d/d B/d E A/0 C/1 由隱含表中的標(biāo)注可知，該狀態(tài)表中的 相容狀態(tài)對有： (A， B)、 (A， C)、 (A， D)、 (A， E)、 (B， D)、 (C， D)、 (C， E)。 ①作隱含表，尋找相容狀態(tài)對。 解： 這是一個(gè)具有 5個(gè)狀態(tài)的原 始狀態(tài)表，表中存在不確定的次態(tài) 和輸出，因此，是一個(gè)不完全確定 狀態(tài)表。 下面舉例說明不完全確定狀態(tài)表的化簡方法。 ? ④作出最小化狀態(tài)表。閉覆蓋表的畫法是：在表的左邊自上而下列出所選相容類，表的中間覆蓋部分從左到右列出全部狀態(tài)，表的右邊閉合部分列出各相容類在輸入各種取值組合下的次態(tài)組合。 尋找最小閉覆蓋要借助于閉覆蓋表。 同時(shí)具備最小、閉合和覆蓋 3個(gè)條件的相容類 (包括最大相容類 )集合，稱為最小閉覆蓋。 b. 最小性，即所選相容類集合中相容類個(gè)數(shù)應(yīng)最少。要想求出不完全給定狀態(tài)表的最小化狀態(tài)表，必須從最大相容類 (或相容類 )中選出一個(gè)相容類的集合，該相容類集合必須滿足以下 3個(gè)條件。 2個(gè)、 3個(gè)、 4個(gè)和 5個(gè)狀態(tài)的最大相容類狀態(tài)合并圖如下圖所示： ?③利用閉覆蓋表，求最小閉覆蓋。狀態(tài)合并圖是一種將不完全確定狀態(tài)表的狀態(tài)，以“點(diǎn)”的形式均勻地繪在圓周上，然后把所有相容對都用線段連接起來而得到的圖。 ? ②利用狀態(tài)合并圖，求出最大相容類。如果與之關(guān)聯(lián)的次態(tài)對都是相容的，則原狀態(tài)對是相容的；只要某方格中填入的次態(tài)對中有一對不相容，則該方格所對應(yīng)的狀態(tài)對不相容，在該方格中填人標(biāo)記“／”。若某個(gè)狀態(tài)對相容，則在相應(yīng)方格中填入“ √”；若某個(gè)狀態(tài)對是不相容的，則在相應(yīng)方格中填入“”；若兩個(gè)狀態(tài)的輸出相同 (或者不確定 )，而其次態(tài)尚不能直接確定是否相容，則在相應(yīng)方格中填入與之相關(guān)的次態(tài)對。利用隱含表尋找相容對的過程與化簡完全確定狀態(tài)表時(shí)尋找等效對的過程是相同的，僅僅是狀態(tài)相容與狀態(tài)等效的標(biāo)準(zhǔn)有所不同而已。其一般步驟與方法如下。由于相容狀態(tài)無傳遞性，所以，同一原始狀態(tài)表的各最大相容類之間可能存在相同狀態(tài)，即同一狀態(tài)可能出現(xiàn)在不同的最大相容類中。 ③ 最大相容類。處于同一相容類中的所有狀態(tài)之間都是兩兩相容的。 ②相容類。 即不能由 S1和 S2相容、S2和 S3相容，推出 S1和 S3也相容。 第二，它們的次態(tài)屬于下列情況之一： a． 次態(tài)相同； b． 次態(tài)交錯(cuò)或?yàn)楦髯缘默F(xiàn)態(tài)； c． 次態(tài)循環(huán)或?yàn)橄嗳輰Γ? d． 其中的一個(gè) (或兩個(gè) )為不確定狀態(tài)。假定狀態(tài) Si和 Sj是不完全確定狀態(tài)表中的兩個(gè)現(xiàn)態(tài)，那么，狀態(tài) Si和 Sj相容的條件，可歸納為在一位輸入的各種取值組合下滿足如下兩條。所有的有效輸入序列，是指有效輸入序列的長度和結(jié)構(gòu)是任意的。假定狀態(tài) Si和 Sj是不完全確定狀態(tài)表中的兩個(gè)狀態(tài)，如果對于所有的有效輸入序列，分別從狀態(tài) Si和 Sj出發(fā)，所得到的輸出響應(yīng)序列 (除不確定的那些位之外 )是完全相同的，那么，狀態(tài) Si和 Sj是相容的，或者說狀態(tài) Si和 Sj是相容對，記作 (Si， Sj)。不完全確定狀態(tài)表的化簡是建立在相容狀態(tài)基礎(chǔ)上的。無疑，這些不確定的狀態(tài)和輸出對于狀態(tài)化簡將是有利的，關(guān)鍵是必須適當(dāng)處理，以確?；喦昂鬆顟B(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)表時(shí)已經(jīng)看到，根據(jù)實(shí)際問題所形成的原始狀態(tài)表除完全確定狀態(tài)表之外，還存在另一類不完全確定狀態(tài)表。 ④作出最小化狀態(tài)表。其次，狀態(tài) D和 G不和任何其他狀態(tài)等效，故它們各自構(gòu)成一個(gè)最大等效類。由所得到的四個(gè)等效對可知，等效對 (A， B)， (A， E)， (B， E)構(gòu)成一個(gè)最大等效類｛ A， B， E}。 由隱含表可知，原始狀態(tài)表中的 7個(gè)狀態(tài)共有四個(gè)等效對： (A， B)， (A， E)， (B， E)， (C， F)。 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”號(hào)，這表明狀態(tài) C和 D不等效。 例如，在圖中，狀態(tài) A、 B對應(yīng)的方格中次態(tài)對為 CF， 而狀態(tài) C、F對應(yīng)的方格標(biāo)有“ √”號(hào)，表明狀態(tài) C和 F等效，由此可判斷出狀態(tài) A和 B等效。 –經(jīng)過順序比較后，還有 A和 B， A和 E， B和 E以及 D和 C共 4個(gè)狀態(tài)對尚未確定是否等效。 例如，狀態(tài)表中 C和 F滿足狀態(tài)等效條件，所以，在隱含表的相應(yīng)方格內(nèi)填入“ √”；狀態(tài) A和 C不滿足等效條件，故在隱含表的相應(yīng)方格內(nèi)填入“”；狀態(tài) A和 E雖然滿足輸出相同這個(gè)條件，但它們的次態(tài)在 x=1時(shí)為 B和 E， 由于當(dāng)前尚不能確定 B和 E是否等效，因此，將 BE填人相應(yīng)方格中。 ②尋找等效對。 B C D E F G A B C D E F 隱含表格式 ④作出最小化狀態(tài)表?？v向從上到下依次為 BG， 橫向從左到右依次為 A~F。根據(jù)畫隱含表的規(guī)則，可得到與給定狀態(tài)表對應(yīng)的隱含表框架如圖所示。用隱含表法化簡如下。 例 . 化簡所示原始狀態(tài)表。確定各最大等效類時(shí)應(yīng)注意兩點(diǎn)：一是各最大等效類之間不應(yīng)出現(xiàn)相同狀態(tài)，因?yàn)槿魞蓚€(gè)等效類之間有相同狀態(tài)，則根據(jù)等效的傳遞性可令其合為一個(gè)等效類；二是原始狀態(tài)表中的每一個(gè)狀態(tài)都必須屬于某一個(gè)最大等效類，換句話說， 各最大等效類所包含的狀態(tài)之和必須覆蓋原始狀態(tài)表中的全部狀態(tài)，否則，化簡后的狀態(tài)表不能描述原始狀態(tài)表所描述的功能。 ③求出最大等效類。若方格內(nèi)的次態(tài)對均為等效狀態(tài)對，則與該方格對應(yīng)的狀態(tài)為等效狀態(tài)，該方格不增加任何標(biāo)志。 關(guān)聯(lián)比較時(shí)，首先要確定隱含表中待檢查的那些次態(tài)對是否等效，并由此確定原狀態(tài)對是否等效。每個(gè)狀態(tài)對的比較結(jié)果有 3種情況，一是明確是等效的，在相應(yīng)方格內(nèi)填上“ √”；二是明確是不等效的，在相應(yīng)方格內(nèi)填上“”；三是與其他狀態(tài)對相關(guān)，有待于進(jìn)一步檢查的，在相應(yīng)方格內(nèi)填上相關(guān)的狀態(tài)對。利用隱含表尋找狀態(tài)表中的全部等效對一般要進(jìn)行兩輪比較，首先進(jìn)行順序比較，然后進(jìn)行關(guān)聯(lián)比較。表中每個(gè)方格代表一個(gè)狀態(tài)對。隱含表是一個(gè)直角三角形階梯網(wǎng)格，橫向和縱向格數(shù)相同，等于原始狀態(tài)表中的狀態(tài)數(shù)減 1。 (2)用隱含表進(jìn)行狀態(tài)化簡 ? 用隱含表法進(jìn)行狀態(tài)化簡的一般步驟如下。 原始狀態(tài)表的化簡過程，就是尋找最大等效類，然后將每個(gè)最大等效類中的所有狀態(tài)合并為一個(gè)新的狀態(tài)，從而得到最小化狀態(tài)表的過程。 換句話說，如果一個(gè)等效類不是任何其他等效類的子集，則該等效類稱為最大等效類。 –③最大等效類：所謂最大等效類，是指不被任何別的等效類所包含的等效類。 根據(jù)等效狀態(tài)的傳遞性，可以從等效對中尋找出等效類。記作 (S1， S2)， (S2，S3)→(S1 ， S3) – ② 等效類：所謂等效類是指由若干彼此等效的狀態(tài)構(gòu)成的集合。 等效狀態(tài)具有傳遞性。而次態(tài)為等效對是