图8-2为一个DFA的状态转换图,与其等价的正规表达式是(31),在图中状态(32)是可以合并的状态。

admin2009-02-15  24

问题 图8-2为一个DFA的状态转换图,与其等价的正规表达式是(31),在图中状态(32)是可以合并的状态。


选项 A、q0和q1
B、q2和q3
C、q1和q2
D、q0和q3

答案B

解析 首先将所有状态分成两个子集,一个由终态组成,一个由非终态组成,即{{q0,q1}, {q2,q3}}。在读入符号1后,状态q0和q1分别转换为第一个子集中的状态q1和第二个子集中的状态q2,所以第一个子集中的状态q0和q1是可区别的;而第二个子集中的状态q2和q3在读入符号0,1后均转换为第二个子集的状态,因此得到了新的划分{{q0},{q1},{q2,q3}};即q2和q3是不可区分的状态,它们可以合并。
   q2和q3在读入符号0,1后均转换为自身的状态,则后面部分可化为结尾部分为字符0和1的任意组合,这时就可以排除(31)题中的B和D选项;再找一个表达式来排除其中的一个答案,可看到表达式一定要能产生1011开头的式子,而C不包括这样的表达式,所以排除C。
转载请注明原文地址:https://kaotiyun.com/show/0TxZ777K
0

相关试题推荐
最新回复(0)