[音乐] 嗨！欢迎回来。
我们在了解了这个构造的有限状态机这么一个机构，
并且呢，得知了有限状态机和正则语言它是一一对应的
这些情况下，我们进一步还能做什么呢？我们说，这个数学
它接下来感兴趣的事情是说，我们定义了这么多的这个对象之后， 我们是不是希望对它们进行一个分类，
因为我们只有掌握了这个分类以及掌握了类别之后，我们就可以更好的理解 这些机器之间它们有什么关联。
所以呢， 这个分类就好像我们在数理逻辑里头讨论这个
命题公式的这个放释一样，有很多的命题公式，它实际上它们的这个真值都是一样的， 那么它所对应的真值函数都一样。
但是呢，能不能找出一种最为规范的形式来代表这一类
这些命题公式呢？那么，我们情况回到有限状态机， 那么也是一样的。
我们希望做一件什么事，就是把有限状态机按照它所识别的这个语言进行分类，
把这个识别同一个语言的所有的机器呢，都给它归在一起，然后呢找一个代表。
那么当然说，我们要找一个代表，要么是说它的形式相当的规范，
像比如说像这个主析取范式一样，它都由这个一个一个的极小项 来构成。
那么，要么呢就是说我们能够找到 一种范式，恩一种形式，像有限状态机，它的比如说
它的状态的数目最少，是不是就可以，啊，这个最少也是基于我们 资源节约的这个原则嘛，是吧。
所以呢， 为了做这个准备，我们先来看看什么叫做机器同余。
那么，机器同余，同余这个词啊我们已经在抽象代数里面见到过了，它无非就是说把这个
等价关系施加在载体元素上，然后呢，看它
对于这个运算有什么样的一个性质的保持。
那我们这呢，同样把这个等价关系也放在这个
有限状态机的状态里边，用一个等价关系，把状态进行归类，
归成几类，然后再看看这个状态转移函数，对这个 等价状态有什么样的一个效果。
所以我们说， 机器同余，它首先呢它是一个等价关系Ｒ，
那么这个等价关系呢，是定义在状态集合s上的一个等价关系。
那么这个等价关系是说，如果对于任意的两个状态s, t， 如果s,
t 呢，是属于同一个等价类，就是sRt的话，
那么就意味着说，对于任意的输入符号x∈A，
都会有这个x，然后经过s的转移以后，
和x经过t的转移以后，那个 它仍然还是遵循这个R的。
也就是说， F(s,x)RF(t,x)这样的， 它还能够具备。
也就是说，同一个等价类，属于同一个等价类的状态，
对于任意的输入而言，它 分别可能都会转移到不同的状态，但是呢，最终转移的这些状态，
相对于这个等价关系来讲，它还是在同一个等价类。
当然，它未必可能会在前面的这个等价类里边，它可能会转移到另外一个
等价类里边，但是呢，最终的这个结论就是说它们还在同一个等价类。
就是同一个等价类的一些状态，经过任意的这个字符的转移，
转移到了这些状态里头，还会属于同一个等价类。
那么如果满足这样一个性质的话，那么我们就把这个 等价关系就称之为机器同余，它就是一个同余关系。
那么就相对于这个状态来讲， 是一个同余，机器同余。
那么这个就是同余的这个定义。
那么我们再回顾一下这个抽象代数当中的这个同余关系。
那么它是说，在代数结构<S, △>， 这个△呢是一个一元运算啊，那么S上的一个等价关系~,
说如果满足说a~b ,就蕴含着△a ~△b,
那么就称作这个~呢，就称作是 S上关于一元运算△的一个同余关系。
那么你看，这个同余关系和机器同余是不是还是同一个意思？
就说，这个同余关系呢是说，如果A和B是在同一个等价类里边，
那么经过运算之后，它的这个运算结果还在同一个等价类里。
那么当然，可能不是ab那种等价类，它可能是另外一些等价类，但是呢，
这儿的关键是，它们还是属于同一个等价类，这就叫同余。
那么，在同余关系下，
代数结构的这个载体元素呢，就会体现出一种所谓的聚类的性质，它聚成一类一类一类。
那么同一类的元素经过运算，它的结果呢，还是同一类。
那么再，再回、 回到有限状态机的这个机器同余里来，
那么它呢，也是把这个状态，表现出一种聚类的性质。
那么这个聚类呢，就是同一个状态，同一类的状态，经过读入任何的字符， 它的目标状态还在同一类。
那么这个呢，实际上描述了一种 某一种等效性。
我们在代数结构里头说，这个载体元素 有一种分类等效性。
那么在有限状态机当中，这个机器同余对于这个状态呢， 也同一个等价类的状态也反映了某种状态的
等效性，那么只要有这个等效性，我们就可以想办法， 构造出来具有状态更少的，我们按
类来分，更少的这个状态的有限状态机。
那么这个呢，就成为一个化简的一个方向。
陈斌副教授
