首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
某一确定有限自动机(DFA)的状态转换图如图2-2所示,与该DFA等价的正规式是(14)。
某一确定有限自动机(DFA)的状态转换图如图2-2所示,与该DFA等价的正规式是(14)。
admin
2015-06-03
62
问题
某一确定有限自动机(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
软件设计师上午基础知识考试
软考中级
相关试题推荐
用于所有网络设备的完整网络管理协议族是(1),它的整体结构建立在(2)参考模型的基础上。网络管理应用进程使用该参考模型中的(3)。在该层上,公共管理信息服务单元(CMISE)提供了应用程序使用(4)协议的接口。SNMP是应用最广泛的网络管理协议,其最新版本
用于所有网络设备的完整网络管理协议族是(1),它的整体结构建立在(2)参考模型的基础上。网络管理应用进程使用该参考模型中的(3)。在该层上,公共管理信息服务单元(CMISE)提供了应用程序使用(4)协议的接口。SNMP是应用最广泛的网络管理协议,其最新版本
网络管理协议中,简单网络管理协议SNMP是(1)协议,它基于(2)协议来传输数据。SNMP提供了4类管理操作,其中(3)操作用来提取特定的网络管理信息。SNMP是通过(4)方式实现管理功能的。在SNMP管理控制框架中定义了管理进程和管理代理,其中网络管理工
可以推断,该网络使用的路由算法最可能是(336)。节点A根据当前的路由信息计算出的到节点D的路由可能为(337)。将路由信息发送到其它节点所采用的基本算法是(338)。为避免路由信息被重复发送,需要给路由信息包编号。设想每秒钟传送一次路由信息,为确保路由信
在TCP/IP网络中,ICMP协议起着差错和拥塞控制的作用,它属于(198)协议,ICMP报文封装在(199)协议数据单元中传送。在ICMP的报文中,常用的ping程序中使用了(200)报文,以探测目标主机是否可以到达。如果在IP数据报传送过程中,发现生命
ATM的155Mb/s接口中,UNI使用(41)。ATM交换机是一个多端口设备,但不可以充当(42)。SMDS是基于IEEE(43)的规范,SMDS数据分组的格式包括(44)。SMDS的说法中,(45)是不妥的。
结构化综合布线系统分为六个子系统,其中水平子系统的作用是(67),干线子系统的作用是(68)。(68)
阅读下列说明和C++代码,将应填入()处的字句写在答题纸的对应栏内。【说明】某图像预览程序要求能够查看BMP、JPEG和GIF三种格式的文件,且能够Windows和Linux两种操作系统上运行。程序需具有较好的扩展性以支持新的文件格式和操作系统
如果两名以上的申请人分别就同样的发明创造申请专利,专利权应授予(10)。
随机试题
能以不衰减的形式沿可兴奋细胞膜传导的电活动是
马克思主义中国化的根本原因是()
A.革兰阳性球菌感染角膜出现B.葡萄球菌C.肺炎球菌D.绿脓杆菌E.摩拉克菌属
患者,男性,69岁。患肺气肿病10年。近日咳嗽、咳痰、气促、精神差。查体:口唇发绀,呼吸30次/分,神志恍惚,多汗和皮肤湿暖,胸廓饱满,肋间隙增宽;动脉血气分析:pH7.31,PaO267kPa,PaCO28kPa。该患者最可能的诊断是
在规定的测量条件下多次测量同一个量所得测得值与计量标准所复现的量值之差是测量的____________的估计值。
甲为一开发商,乙为一苗圃经营商,甲将已出卖的楼房的房顶租于乙进行苗圃种植。因乙在房顶种植花草浇水引起纠纷。以下表述正确的是()。
下列属于公司高级管理人员的是()。
某企业分配给产品部的IP地址块为221.55.31.192/26,分配给市场部的IP地址块为221.55.31.160/27,分配给财务部的IP地址块为221.55.31.128/27,那么这三个地址块经过聚合后的地址为()。
A、 B、 C、 B本句为提议要给对方检查产品报告书的一般疑问句。
Peoplehavebeenfondofrosessincethebeginningoftime.Infact,itissaidthatthewiseandknowingConfuciushada600-bo
最新回复
(
0
)