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

admin2015-06-03  35

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

选项 A、10*(0|1)*
B、((0*0)*1*)*
C、1*((0|1)00)*
D、(1*(01*0)*)*

答案D

解析 本题主要考察有限自动机和正规式,这个知识点也是考试中的重点和难点。
    对于判断一个有限自动机与那个正规式等价,常见的方法是分析有限自动机,清楚有限自动机所表示的含义和特性,然后用排除法找到与该有限自动机等价的正规式。
    对于本题,首先分析题目中给出的状态转换图,由图可知,状态q0为唯一的终态,也是初态,那么从初态到终态可以不输入然后字符,因此该有限自动机可识别空串。
    另外,仔细分析有限自动机,不难发现,以一个0离开状态q0然后再以一个0返回状态q0。那么从初态到终态输入0的个数必须是偶数,而该有限自动机只能识别0和1两种字符。因此该自动机识别的串是包含偶数0的二进制代码串。
    清楚了该有限自动机的特性和含义后,我们再逐个分析四个正规式。
    在正规式1*0(0|1)木中,不能确保O的个数是偶数,而不能表示空串(因为所有闭包取空,结果仍然有一个1),因此这个正规式肯定不与有限自动机等价。
    在正规式((0*0)*1*)*中,可以表示空串,但不能确保O的个数是偶数,因此也不等价于题目给出的有限自动机。
    同样的道理,可知正规式1*((0|1)00)*也不与题目给出的有限自动机等价。
    而在正规式(1*(01*0)*)*中,即可以表示空串,也由于(01*0)这部分不管重复多少次,都能确保0的个数是偶数,因此等价。
转载请注明原文地址:https://jikaoti.com/ti/IGf7FFFM
0

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