首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
某一确定有限自动机(DFA)的状态转换图如图2-2所示,与该DFA等价的正规式是(14)。
某一确定有限自动机(DFA)的状态转换图如图2-2所示,与该DFA等价的正规式是(14)。
admin
2015-06-03
61
问题
某一确定有限自动机(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://www.kaotiyun.com/show/WCRZ777K
本试题收录于:
软件设计师上午基础知识考试题库软考中级分类
0
软件设计师上午基础知识考试
软考中级
相关试题推荐
网络管理协议中,简单网络管理协议SNMP是(1)协议,它基于(2)协议来传输数据。SNMP提供了4类管理操作,其中(3)操作用来提取特定的网络管理信息。SNMP是通过(4)方式实现管理功能的。在SNMP管理控制框架中定义了管理进程和管理代理,其中网络管理工
IEEE802.11定义了无线局域网的两种工作模式,其中的(208)模式是一种点对点连接的网络,不需要无线接入点和有线网络的支持,它通过把一组需要互相通讯的无线网卡的ESSID设为同值来组网。IEEE802.11的物理层规定了三种传输技术,即红外技术、直接
为了进行差错控制,在局域网中对数据帧广泛使用的校验方法是(178)校验。CRC-16规定的生成多项式为G(x)=X16+X15+X2+1,它产生(179)位的校验码,当接收端发现错误后会(180)。如果CRC的生成多项式为G(X)=X4+X+1,码字为10
如图3.1所示,如果为曼彻斯特编码,则表示的数据可能为(283),下面的各种网络中,适用这种编码的是(284)。为了在广域网上高速传输数字信号,可用(285)的编码方式,其编码效率为(286)。设某编码体制的编码方法为:输入数据(m=1,2,…),发送时,
如图2.1所示,有四台Linux主机进行互联,则实现PC1与PC4之间互访的步骤应该是:1.首先运行(29)命令关闭计算机,在PC2与PC3上添加第二块网卡(ethl)后重新启动;2.在PC2与PC3上为第二块网卡分配IP地址,并激
建筑物综合布线系统中的工作区子系统是指__________。(2009年下半年试题)
编写汇编语言程序时,下列寄存器中,程序员可访问的是__________。(2010年下半年试题)
阅读下列说明和C代码,回答问题1至问题3,将解答写在答题纸的对应栏内。【说明】给定一个字符序列B=b1b2…bn,其中bi∈{A,C,G,U}。B上的二级结构是一组字符对集合S={(bi,bj)},其中i,j∈{1,2,…,n},并满足
赵某于2002年4月1日申请一项外观设计专利,2003年2月8日获得授权,这项专利权的保护期限终止于(12)。
李富是某公司的产品设计部的设计师,他经过努力工作,研究出了一种新的产品外形,该公司利用这一设计制造出新的产品后,致使销量大增。同时,对该设计申请了专利保护,那么其专利权应该归()所有。
随机试题
世界上最早出现集体协议的国家是()
寒湿困脾证与湿热蕴脾证的鉴别要点有
有关洗手的注意事项,错误的是
建设工程项目的信息管理是通过对()的管理,使项目的信息能方便和有效地获取、存储、存档、处理和交流。
由于全球金融危机,电脑制造行业进行了行业内的分析,统计数据表明,该行业内市场占有率前五名的企业为A、B、C、D、E,市场占有率分别为29%、25%、21%、15%和10%。其中E公司为了制订自身的发展战略,采用著名的五力模型对行业的竞争结构进行了分析,其分
Itissimplyunacceptablethatthepooresthalfoftheworld’spopulationowns__________afewdozensuper-richpeoplewhocould
人本管理的核心是()。
在民主革命和社会主义革命的关系问题上,中国共产党内曾出现不同的观点和主张,实践证明,正确的是()。
半强有效市场[中央财经大学2011金融硕士]
Text…DramaticPeakDistrict,withitsgenuinesteepfells,neverfailstoastonishme.Acarwill【C1】______youallround
最新回复
(
0
)