(2)化简举例例化简下表所示原始状态表。解①作隐含表给定原始状态表具有7个状态，根据画隐含表的规则，可画出隐含表框架如下。第30页，共56页，星期日，2025年，2月5日②寻找等效对根据等效状态的判断标准，依次检查每个状态对，可得到顺序比较结果如图(a)所示。关联比较的结果如图(b)所示。图(a)图(b)第31页，共56页，星期日，2025年，2月5日由判断结果可知，原始状态表中的7个状态共有四个等效对：(A，B)，(A，E)，(B，E)，(C，F)。第32页，共56页，星期日，2025年，2月5日④状态合并，作出最小化状态表令{A,B,E}----a、{C,F}---b、{D}---c、{G}---d，并代入原始状态表中，即可得到化简后的状态表如下边右表所示。③求出最大等效类由所得到的等效对和最大等效类的定义可知，原始状态表中的7个状态共构成{A,B,E},{C,F},{D},{G}四个最大等效类。第33页，共56页，星期日，2025年，2月5日二、不完全确定状态表的化简不完全确定状态表中存在不确定的次态或输出，这些不确定的状态和输出对于状态化简是有利的，关键是必须恰当处理，以确保化简前后状态表的逻辑功能不变。为此，引入出了一个新的概念--相容状态。1．相容状态和相容类
?
???（1）相容状态?
???①定义?
???假定状态Si和Sj是不完全确定状态表中的两个状态，如果对于所有的有效输入序列，分别从状态Si和Sj出发，所得到的输出响应序列(除不确定的那些位之外)是完全相同的，那么，状态Si和Sj是相容的，或者说状态Si和Sj是相容对，记作(Si，Sj)。
???有效输入序列：从状态表中的状态S出发，如果给定某输入序列所得到的状态响应序列除最后一个次态外，其他次态都是确定的，那么，这个输入序列对状态S是有效的。所有的有效输入序列，是指有效输入序列的长度和结构是任意的。第34页，共56页，星期日，2025年，2月5日②相容状态的判断
???假定状态Si和Sj是不完全确定状态表中的两个现态，状态Si和Sj相容的条件可归纳为在一位输入的各种取值组合下满足如下两条。
???第一，它们的输出完全相同，或者其中的一个(或两个)输出不确定。
???第二，它们的次态属于下列情况之一：
???a.次态相同；
???b.次态交错或为各自的现态；
???c.次态循环或为相容对；
???d.其中的一个(或两个)为不确定状态。③注意!!相容状态不具有传递性。这是因为判断两个状态是否相容时，对于不给定的输出和不给定的次态可以随意指定的缘故。例如，在表中，有状态A、B相容，状态A、C相容，但状态B、C不相容。现态y次态/输出(y（n+1）/Z)x=0x=1ABCDA/0A/0A/0B/1D/dD/0D/1d/1第35页，共56页，星期日，2025年，2月5日(2)相容类
???相容类是由彼此相容的状态构成的集合。处于同一相容类中的所有状态之间都是两两相容的。例如，若有相容对(S1,S2)、(S2，S3)和(S1,S3)，则可构成相容类{S1,S2，S3}。(3)最大相容类
???若一个相容类不是任何其他相容类的子集，则该相容类称为最大相容类。由于相容状态无传递性，所以，同一原始状态表的各最大相容类之间可能存在相同状态，即同一状态可能出现在不同的最大相容类中。第36页，共56页，星期日，2025年，2月5日2.不完全确定状态表的化简?
???(1)化简步骤?
???一般步骤如下：
???①作隐含表，寻找相容状态对。
???利用隐含表寻找相容对的过程与化简完全确定状态表时寻找等效对的过程是相同的，仅仅是状态相容与状态等效的标准有所不同而已。即在顺序比较完成后，可利用已建立的隐含表继续进行关联比较，直至判断出所有状态对相容或不相容为止，便可列出原始状态表中的全部相容对。
???②利用状态合并图，求出最大相容类。
???状态合并图：状态合并图是求最大相容类工具。它将状态表的所有状态以点的形式均匀地绘在圆周上，然后把所有相容对用线段连接起来。若某些顶点任意两点之间都有连线，则其顶点状态的集合构成一个最大相容类。第37页，共56页，星期日，2025年，2月5日图(a)、(b)、(c)分别表示包含3个、4个和5个状态的最大相容类状态合并图。第38页，共56页，星期日，2025年，2月5日③利用闭覆盖表，求最小闭覆盖。
???最小闭覆盖-----是从最