[音乐] 嗨，欢迎回来。 到目前为止呢，我们所看到 的这个有限状态机不管是它多简化多优美也好 它好像这个智商还低了点 它只会说，对一个输入的字符串说yes sir或者说no sir，它只会做出识别或者不识别这种 这种命令也好，这种指令。 那么接下来我们来看看更加聪明一些的 这个有限状态机，就是带输出的机器，这不得了，它还可以做一些额外的一些事情 那么带输出的有限状态机呢在我们 原来的有限状态机M(A,S,Y,s0,F)这个基础上 首先呢去掉这个接受状态这个集合Y 也就是说它不再说yes或no了 而是会做一些事情，那么这个做的事情呢就是增加一个输出字符的有限集合Z 然后呢还有一个输出函数 因为除了这个状态转移之外，状态的 只是它的一个机器的内部记忆或者内部的一个归类的一种，一种形式 那么它需要对外部有所贡献的话，那么那就需要一个输出函数 这个输出函数G呢就是也是从一个状态开始 读入一个字符，完了以后同时它会有一个输出字符 所以有一个输入就会有一个输出，这就是一个输出函数 那么这个呢就意味着在状态转移的同时它会输出一个字符 那么状态转移函数是SxA到S 那么输出函数是SxA到Z，是输出一个字符的 那么它的这个工作的方式 就是这样。 我们看看下边的这个机器的这个样子呢 那中间这个八边形也是一个机器，那么它呢也有一些内部的状态 那有一个指针会在状态之间来回的这个旋转 根据这个状态转移函数。 那另外呢它还会有一个机构 是吧，我们可以想象一下像齿轮一样，哐当转过去输出一个z 转过去输出一个z。 那么从a1，a2一直到am开始输出 a输出一个，输入一个a1，那么它状态转移一下，然后同时输出一各z1 然后a2进去了以后，状态再转移，输出一个z2 然后到am，输出一个zm。 所以呢输入有多长，输出也会有多长 然后状态呢也会转移多少次。 这就是有限状态机的这种工作的方式 所以呢，它对于输入字符串u，a1，a2一直到am，就相当于印在一个输入纸带上 然后这个机器呢逐个的读入这个输入带的字符 然后同时呢进行状态转移，这个状态转移的序列呢V就等于s0，s1，s2一直到sm 然后同时呢在这个输出带上逐个的把这个输出字符给打印出来 读入一个，打印一个，读入一个，打印一个，那么这个打印的字 符呢从z1，z2……zm，就把它收集在一起，就 相当于它输出了一个w。 读入u，然后状态转移V 然后得到一个输出字符串w，这就是输入，状态转移，输出这样的一个模式 好我们先来看看它能做什么事，当然最简单的可以做加法 我们回想起在数理逻辑那一，那一章里面 我们构造过一个二位的加法器，这是一个作业哈 这构造过一个二位的加法器，我们就知道它用了 即便是化简化得最简我们也用了13个门电路 但如果想象如果是32位的加法器，它要用多少门电路 如果是无穷多位的加法器的话，那么该怎么办？ 那可能会越来越复杂，越来越复杂，但是我们有限状态机呢 可以为这个加法器这个事业在贡献一些。 我们来看看这个 实现二进制加法的这个有限状态机它是什么样子的 这个它是由两个二进制数的加法，那么 而且呢这个二进制数的这个位数是 不限的，也就是说你可以做1位的加法 也可以做100位，1000位甚至10000位，反正就没有，这个位数是没有限制 什么时候停，我们会用一个特殊符号数说"停"这样 那么在停之前它都会不断地输出这个加法的结果 那么这样呢我们既然是两个二进制数相加，那么它肯定一个数会大一些，一个数会小一些 那么它的长短会不一样，那没关系，我们可以给那个比较短数前面补上0 它不会改变它的数值，但是呢会改变它的长度，那么使得两个数呢具有相同的这个长度 接下来呢我们把两个数它的对应 位进行组合，然后从低位开始输入到机器里边去 那么最后我们会输入一个特别的字符，空白，就表示输入结束了 所以呢我们看下边这个式子，1101011加上 111011它应该等于10100110这么一个结果 那么我们在这个机器里头输入的时候，我们做一个安排 就是把它对应的位数进行组合，比如我们会输入11，从低位开始 按照这些条，11，再输入11，再输入00，再输入11，再输入一个01 11，10，最后输入一个b代表结束 那么输出呢，它就应该也是从低位到高位反 向输出，输出0，1，1，0，0，1，0，1 啊，这么一个输出，好。 我们的加法器呢最后在输出了最后一个1的时候 计算就结束了，进入了一个叫做停机的状态，停机状态 那我们从其实从这个有限状态机的工作过程当中 可以知道，这种机器呢它必然会停机，而且它的运行的步数 运行多少步它是确定的，我输入有多少，输入n个字符，它运行n步 然后输入一旦停止，这个机器马上就停下来 当然我们这里头我们要强调这个停机，实际上呢停机可不是一件很容易的事情 对于有限状态机来讲，停机非常的简单，输入停止，机器就马上停下来，输出也马上停下来 而对于其它的机器而言，可就不是这么简单的事情，我们在后面谈到图灵机的时候 停机问题其实是一个大问题，当你输入结束的时候 这个按照规则进行来回走的时候，它有可能会不停机，永远都不会停 机，这类似于我们在程序设计当中编了一个程序陷入了死循环，它永远都不会停 那么那是另外一回事了哈。 我们接下来还是回到，看看这个有 做计算的有限状态机呢。 那么我们构造了这个二进制加法的有限状态机呢 就是这个样子的，它有3个状态组成，一个c，一个n，一个s，这个3个状态 然后每个状态它的输入集合，它就是输入集，输入字符就是00011011 和作为结束的空白b，对吧。 那么这个s呢 状态就有执行状态（c），初始状态（n）和停止 状（s），这么3状态。 其中你只要进入了这个（s）这个状态以后 它就不再接受任何的字符输入了 那么这个输出的字符呢，就这0,1或者b，b呢就是最后停机时候输出的那个 所以我们可以观察哈，从00开始 我们这00其实就是0+0了，0+0那么还是输出0 那么还回到这个初始状态，那么1+0输出一个1 然后0+1呢也输出1，都还停留在这个初始状态 但是呢一旦有这个1+1，它就会产生一个进位 所以呢它输出的一个0，因为1+1等于10嘛，那么输出一个0转移到这个 执行这个状态转移到（c）这个状态，那么（c）这个状态我们就要记住，它始终有个进- 位需要加 所以在（c）这个状态里头0+0就，它就应该 输出一个1，然后同时呢转移到（n）这个没有进位的状态里去 其它的也好处理了 1+0那就相当于1+0再加1，它还是输出0 然后还回到有一个进位的这个状态（c）对吧。 那么其它，一旦碰到b 在有进位的时候，碰到结束符b，就把进位输出，输出个1，然后停止状态 那么没有进位的状态下输入，得到读入b的话，那么它没有什么可输出的，那就输出一个b 然后转移到停机这个状态，所以呢这个就是 能够实现二进制加法的有限状态机
