首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
某一确定性有限自动机(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
30
问题
某一确定性有限自动机(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
数据库系统工程师上午基础知识考试
软考中级
相关试题推荐
已知某系统由ABCDEF六个活动构成,项目实习人员根据活动逻辑关系及历时等信息绘制了该系统的网络图,并给出了该系统的工期为9周。项目组其他成员纷纷提出意见。以下意见中,____________是正确的。
项目风险识别是指找出影响项目目标顺利实现的主要风险因素,并识别出这些风险究竟有哪些基本特征、可能会影响到项目的哪些方面等问题。以下关于项目风险识别的叙述中,正确的是:()。
根据GB/T-17544,软件包质量要求包括三部分,即产品描述要求、()、程序和数据要求。
(2014下集管)信息系统通过试运行,系统的各种问题都已经暴露在用户面前,这时通常可以考虑进入______阶段。
(2007上系分)关于UML中的状态图和活动图的叙述中,______是错误的。
(2005上项管)UML提供了4种结构图用于对系统的静态方面进行可视化、详述、构造和文档化。其中______(1)是面向对象系统建模中最常用的图,用于说明系统的静态设计视图;当需要说明系统的静态实现视图时,应该选择______(2);当需要说明体系结构的静
(2005上项管)项目小组建设对于项目的成功很重要,因此,项目经理想考察项目小组工作的技术环境如何,有关信息可以在______中找到。
(2005下项管)一个产业的竞争状态取决于五种基本竞争力量:新竞争者的进入、替代品的威胁、买方的讨价还价能力、供应者的讨价还价能力以及______。
(2011下集管)配置项的版本号规则与配置项的状态相关,以下叙述中正确的是______。
(2008上系分)某个系统在开发时,用户已经定义了软件的一组一般性目标,但不能标识出详细的输入、处理及输出需求;开发者也可能暂时不能确定算法的有效性、操作系统的适应性或人机交互的形式。在这种情况下,采用______开发最恰当。
随机试题
在考生文件夹下有一个数据库文件“samp3.accdb”,里面已经设计了表对象“tEmp”、窗体对象“fEmp”、宏对象“mEmp”和报表对象“rEmp”。同时,给出窗体对象“fEmp”的“加载”事件和“预览”及“打印”两个命令按钮的单击事件代码,请按以
肉芽组织
集权
CSTNet指的是()
由业主提供的工程担保有()。
凭证审核、记账、查询、结账由操作员BB审核凭证并签章,记账,查询银行存款日记账,查询科目汇总表,结账。
太阳风中的一部分带电粒子可以到达M星表面,将足够的能量传递给M星表面粒子,使后者脱离M星表面,逃逸到M星大气中。为了判定这些逃逸的粒子,科学家们通过三个实验获得了如下信息:实验一:或者是X粒子,或者是Y粒子;实验二:或者不是Y粒子,或者
APA是()的简称。
影响人身心发展的因素主要有()
公有制的主体地位主要体现在()。
最新回复
(
0
)