2. 计算机
  3. 某一确定有限自动机(DFA)的状态转换图如图2-2所示，与该DFA等价的正规式是( )。

某一确定有限自动机(DFA)的状态转换图如图2-2所示，与该DFA等价的正规式是( )。

admin2017-08-31  36
问题 某一确定有限自动机(DFA)的状态转换图如图2-2所示，与该DFA等价的正规式是(    )。
选项 A、10*(0｜1)*
B、((0．0)*1*)*
C、1*((011)00)*
D、(1*(01*0)*)*
答案D
解析 本题主要考察有限自动机和正规式，这个知识点也是考试中的重点和难点。
对于判断一个有限自动机与那个正规式等价，常见的方法是分析有限自动机，清楚有限自动机所表示的含义和特性，然后用排除法找到与该有限自动机等价的正规式。
    对于本题，首先分析题目中给出的状态转换图，由图可知，状态q0为唯一的终态，也是初态，那么从初态到终态可以不输入然后字符，因此该有限自动机可识别空串。
    另外，仔细分析有限自动机，不难发现，以一个0离开状态q0然后再以一个0返回状态q0。那么从初态到终态输入0的个数必须是偶数，而该有限自动机只能识别0和1两种字符。因此该自动机识别的串是包含偶数0的二进制代码串。
    清楚了该有限自动机的特性和含义后，我们再逐个分析四个正规式。
    在正规式1*0(011)*中，不能确保0的个数是偶数，而不能表示空串(因为所有闭包取空，结果仍然有一个1)，因此这个正规式肯定不与有限自动机等价。
    在正规式((0*0)*1木)木中，可以表示空串，但不能确保0的个数是偶数，因此也不等价于题目给出的有限自动机。
    同样的道理，可知正规式1*((0｜1)00)*也不与题目给出的有限自动机等价。
    而在正规式(1*(01*0)*)*中，即可以表示空串，也由于(01*0)这部分不管重复多少次，都能确保0的个数是偶数，因此等价。
转载请注明原文地址:https://kaotiyun.com/show/9NRZ777K
本试题收录于： 软件设计师上午基础知识考试题库软考中级分类
0

软件设计师上午基础知识考试

软考中级

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