编译原理学习笔记（十四）~识别={0,1}上能被能5整除的二进制数

题目

例：识别 ={0,1}上能被能5整除的二进制数

正解

解释：

• 状态0、1、2、3、4表示被5除后余数为0 1 2 3 4 的时候（就是圆圈中的数字表示余数为多少）
• 机器对于一个二进制数字，是从左到右，逐个数字扫描。比如二进制数字10010，机器先读入的数字是1，再是0, 0，1, 0。
• 所以第一个读入的数字不是0就是1。如果是0，那么被5除后余数是0（后面统称余数），进入0状态；如果是1，那么余数就是1，进入1状态。
• 第二个读入的数字也不是0就是1.但是这里需要我们对第一个数字分情况进行讨论：如果第一个数字是0，第二个数字是0，那么余数为0（这时数字是00=0），由0状态转向0状态；
• 如果第一个数字是0，第二个数字是1，那么余数是1（这时数字是01=1），由0状态转向1状态；
• 如果第一个数字是1，第二个数字是0，那么余数是2（这时数字是10=2），由1状态转向2状态；
• 如果第一个数组是1，第二个数字也是1，那么余数是3（这时数字是11=3），由1状态转向3状态。【A状态转向B状态，其中A状态是前面已经确定数字的余数，B状态是加上最后一个数字最终的状态】
• 之后的步骤就是以此类推了，仔细一点就可以了，不用着急。
• 注意：状态0既是起始状态又是结束状态