首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
某一确定性有限自动机(DFA)的状态转换图如图6-5所示,令d=0|1|2|…|9,则以下字符串中,不能被该DFA接受的是(3),与该DFA等价的正规式是(4)。 (其中,ε表示空字符) ①3857 ②1.2E+5 ③-123 ④.
某一确定性有限自动机(DFA)的状态转换图如图6-5所示,令d=0|1|2|…|9,则以下字符串中,不能被该DFA接受的是(3),与该DFA等价的正规式是(4)。 (其中,ε表示空字符) ①3857 ②1.2E+5 ③-123 ④.
admin
2019-03-04
31
问题
某一确定性有限自动机(DFA)的状态转换图如图6-5所示,令d=0|1|2|…|9,则以下字符串中,不能被该DFA接受的是(3),与该DFA等价的正规式是(4)。 (其中,ε表示空字符)
①3857
②1.2E+5
③-123
④.576E10
选项
A、(-d|d)d*E(-d|d)d*|(-d|d)*.d*(ε|E(-d|d)d*)
B、(-d|d)dd*(.|ε)d*|(ε|E(-d|d)d*)
C、(-|d)dd*E(-|d)d*|(-d|d)dd*.d*(ε|E(-|d)d*)
D、(-d|d)dd*E(-d|d)d*|(-d|d|)dd*.d*(ε|E(-dd*|dd*))
答案
A
解析
题目第一问是判断备选答案中有哪些字符串不能被DFA接受。现在逐个对其进行判别,这样有利于对DFA功能的理解和后面的解题。
首先看3857,这个字符串中的元素全部是数字,从DFA的初态0输入一个数字,进行到状态1,在状态1输入数字还是回到状态1,如果还想往后走,必须要输入字符“.”或是字符“E”,但3857中不存在这样的字符,所以无法到达终态,因此①不能被 DFA接受。
接着看1.2E+5,这个不用判断就知道不行,因为“+”在此DFA中无法识别。
再看-123.,此串能从始点顺利到达终点(状态0→状态4→状态1→状态1→状态 1→状态5),所以此串可以被DFA接受。
最后看.576E10,第一个字符“.”在初始状态无法被识别,所以此串也不能被DFA识别。
接下来是把DFA转化为正规式,我们用排除法来解这个题,首先可以排除的是B和D,很明显(-d|d)dd*所表达的串会比DFA所描述的串多一个d。
再看C选项(-|d)dd*E(-|d)d*|(-d|d)dd*.d*(ε|E(-|d)d*)。其中的(-|d)dd*E(-|d)d*表示的路径是不经过状态5的路径。后面的(-d|d)dd*.d*(ε|E(-|d)d*)是指经过状态5的路径。这里的(-d|d)dd*,也是多出了一个d,所以C也可以排除,答案就只能是A了。
转载请注明原文地址:https://kaotiyun.com/show/JtTZ777K
本试题收录于:
数据库系统工程师上午基础知识考试题库软考中级分类
0
数据库系统工程师上午基础知识考试
软考中级
相关试题推荐
配置管理是软件生命周期中的重要控制过程,在软件开发过程中扮演着重要的角色。按照GB/T11457一2006《软件工程术语》的描述,以下关于配置管理基线的叙述中,(13)是不正确的。
项目组合管理是一个保证组织内所有项目都经过风险和收益分析及平衡的方法论。作为公司的项目经理进行项目组合管理时,___________应是重点考虑的要素。
信息的_________要求采用的安全技术保证信息接收者能够验证在传送过程中信息没有被修改,并能防范入侵者用假信息代替合法信息。
任何组织的能力都是有限的,任何组织的资源也都是有限的。公司在选择项目优先级时经常用到DIPP分析法。以下关于DIPP的理解中,不正确的是:()。
在面向对象系统中,()关系表示一个较大的“整体”类包含一个或多个“部分”类。
为了保护网络系统的硬件、软件及其系统中的数据,需要相应的网络安全工具。以下安全工具中,()被比喻为网络安全的大门,用来鉴别什么样的数据包可以进入企业内部网。
根据GB/T-17544,软件包质量要求包括三部分,即产品描述要求、()、程序和数据要求。
(2012上集管)数据库管理系统是操纵和管理数据库的大型软件,用于建立、使用和维护数据库。以下关于数据库管理系统的描述,______是不正确的。
(2007下监理)文件存储设备中,______不支持文件的随机存取。
(2010上系分)______适用于描述复杂算法的执行流程。
随机试题
Thinnerisn’talwaysbetter.Anumberofstudieshave【C1】________thatnormal-weightpeopleareinfactathigherriskofsomedi
命题分为_________、_________和__________。
Onlyinafewcountries______enjoyareasonablestandardofliving.
患者,女,68岁。3年前出现记忆力问题,过去注意仪表,近期出现找不到回家的路,不洗澡换衣。护士在与精神病患者沟通时重要的技巧是
共同危险行为[武大2020年研;北科2014年研;北航2011年研]
在工程量清单计价方式中,清单项目的工程量计算通常是计算其()。
下列工作步骤中属于定额单价法,但不属于实物量法的是()。
土石方平衡应遵循()的原则。
关系营销的核心是()。
【S1】【S2】
最新回复
(
0
)