字节y1以及进位c0相加产生和的字节z1和一个进位字节c1.pptVIP

例9.2.6 构造二进制非负整 数加法器的有限状态机。 解：当(xn…x1x0)2和 (yn…y1y0)2相加时，过程如下： 首先字节x0和字节y0相加产生 和的字节z0和一个进位字节c0， 这个进位或者是0或者是1，然后字节x1、字节y1以及进位c0相加产生和的字节z1和一个进位字节c1，这个过程进行n步，直到字节xn、字节yn以及前一个进位字节cn-1相加产生和的字节zn和一个进位字节cn，这个字节cn就是和的字节zn+1。 完成这个加法器的有限状态机只 用到两个状态，为简单起见，我 们假设字节xn和字节yn都为0， (这样我们就不用考虑和中的字节 zn+1了)，初始状态s0为了记住前 一个进位是0(或者最右面的两个 字节相加)，另外一个状态s1，是 为了记住前一个进位是1的。因为 这个状态机的输入是两个字节的对，所以有四个可能的输入，我们记为00，01，10，11(分别代表第一个和第二个字节)，转换和输出根据由输入的两个字节代表的和与状态代表的进位来构造。例如，当状态为s1，输入是01，则下一个状态为s1，输出为0，因为和是0+1+1=(10)2。这个状态图见图9.2.5。 例9.2.7 在一些编码方案中， 如果一个信息中连续出现3个1， 那么接收者就知道出现了传输 错误，构造一个有限状态机当 且仅当最后收到的三个字节都 是1的时候，它的输出是1。 解：这个状态机有三个状态，初始状态s0记着前一个输入的值，如果前一个输入存在，说明它不是1。状态s1记着前一个输入是1，如果前一个输入的再前一个输入存在，则它不是1。 状态s2记着前两个输入都是1， 输入1可以把状态s0变成状态s1， 因为现在被读入的只有一个1， 而不是两个连续的1；可以把 状态s1变成状态s2，因为现在 被读入的是两个连续的1；可 以把状态s2变成它自身，因为 现在被读入的至少是两个连续的1。一个输入0把任何状态都变成状态s0，因为它打破串中1的连续性。当一个1被读到，并且转换是从状态s2到自身的时候，输出为1，因为结合输入和状态我们可以知道我们已经读到了连续的3个1。所有其它的输出都是0， 状态图如图9.2.6所示。 图9.2.6中所给的有限状态机是语言识别器的例子，因为它的输出为1当且仅当至今读到的输入串具有指定的性质，语言识别是有限状态机的一个重要的应用。 许多不同类型的有限状态机用来模拟计算，这一节所给的有限状态机是带有输出的有限状态机，也称为Mealy机，还有另外一种很重要的带有输出的有限状态机，它的输出只由状态决定。这种状态机就是Moore机。 例9.2.7表明了一个Mealy机是如何用于语言识别的，然而，另外一种没有输出的有限状态机也通常用于这个用途。没有输出的有限状态机也称为有限状态自动机，它有一组终止状态集合，一个符号串被识别当且仅当这个符号串让初始状态变到终止状态，我们将在下一节学习这种类型的有限状态机。 §9.3 没有输出的有限状态机 有限状态机的一个最重要的应 用是语言识别。这个应用在程 序语言编译器的设计和构造中 起着最基本的作用。在上一节 中我们看到，有输出的有限状 态机可以用来识别一个语言，然而， 有另外一些类型的有限状态机是专门为语言识别设计的，它没有输出，但有许多终止状态，一个被识别的串可以让这个状态机从初始状态变到某个终止状态。 在讨论没有输出的有限状态机之前，我们先引入一些重要的概念。我们要定义的一些运算将在讨论语言识别中广泛地被用到。 定义9.3.1 设A和B是V*的子 集，其中V是字母表，A和B的 串联，记为AB，是所有形为xy 的串的集合，其中x是来自A中 的串，y是来自B中的串。 例9.3.1 设A={0，11}， B={1，10，110}，请给出AB和BA。 解：集合AB包含所有A中的串和B中的串的串联，因此， AB={01,010,0110,111,1110,11110}， 集合BA包含所有B中的串和A中的串的串联，所以， BA={10,111,100,1011,1100,11011}。 * 吉林大学远程教育课件 主讲人: 杨凤杰 学 时：64 (第五十七讲) 离散数学 图9.2.5 加法器的有限状态机 10,0 01,0 00,1 10,1 s1 s0 开始 00,0 01,1 11,0 11,1 图9.2.6输出为1当且仅当至今为止读到的输入串以111结尾的有限状态机 s1 0,0 0,0 0,0 s0 s2 开始 1,0 1,0 1,1 *