+  发表主题
老师参与

第三章练习题的一个疑问

zczfsrkqlssjddsbbs 发表于2017年09月19日
<p>13</p><p>DFA M(见图)接受的字集为( )。</p><p><br ></p><p><br ></p><p>A.</p><p>以0开头的二进制数组成的集合<br ></p><p><br ></p><p>B.</p><p>以0结尾的二进制数组成的集合<br ></p><p><br ></p><p>C.</p><p>含奇数个0的二进制数组成的集合<br ></p><p><br ></p><p>D.</p><p>含偶数个0的二进制数组成的集合</p><p><br ></p><p><strong>老师，请问这个题目的状态机不能是不是不能包含所有的含有偶数个0的二进制数？</strong></p>
举报
1 回复
    陈鄞

    1楼

  • 陈鄞 发表于2017年09月20日
    2 | 2 | 举报
    <p>你好！</p><p>&nbsp; &nbsp;&nbsp;</p><p>&nbsp;&nbsp;&nbsp;&nbsp;我没太理解你问题中的“不能是不是不能”是什么意思？<br ></p><p>&nbsp; &nbsp; 那我就直接讲讲这道题的思路吧。</p><p></p><p>&nbsp;&nbsp;&nbsp;&nbsp;根据该图，初始状态是X，而X所在节点为双圈，说明该节点同时也是终止状态。</p><p>&nbsp; &nbsp; 从初始状态X接收到一个0以后，进入到状态Y，此时，无论再遇到多少个1，始终处于状态Y，直到遇到第2个0，才回到终止状态X。此时已扫描的符号串中含有两个也就是偶数个0。</p><p>&nbsp; &nbsp; 如果输入带上还有符号，并且是0的话，根据FA的最长子串匹配原则，FA将继续向前扫描，进入状态Y，之后，无论再遇到多少个1，始终处于状态Y，直到遇到第4个0，才又回到终止状态X。此时已扫描的符号串中含有四个也就是依然是偶数个0。</p><p>&nbsp; &nbsp; 此过程可能一直循环下去，但是每当回到终止状态X时，已扫描的符号串中肯定含有偶数个0。因此，该自动机接受的字集为“含偶数个0的二进制数组成的集合”。</p><p><br ></p>
    陈鄞 发表于2017年09月20日
    2 | 评论(2) | 举报
    • zczfsrkqlssjddsbbs 2017年09月20日
      0 | 举报
      不好意思老师，当时打字的时候光标错位了，我的意思是“是不是不能包含所有的偶数个0的二进制数”，比如1001也是包含偶数个0，但是却不是能识别的语言。
      zczfsrkqlssjddsbbs 发表于2017年09月20日
      0 | 举报
    • 陈鄞 2017年09月20日
      0 | 举报
      <p>你好！</p><p>&nbsp;&nbsp;&nbsp;&nbsp;你说的很对！<br ></p><p>&nbsp;&nbsp;&nbsp;&nbsp;严格来讲，应该是“空串或以0开头的含偶数个0的二进制数组成的集合”。<br ></p><p><br ></p>
      陈鄞 发表于2017年09月20日
      0 | 举报
    添加评论
发表回复