首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
某一确定有限自动机(DFA)的状态转换图如图2-2所示,与该DFA等价的正规式是( )。
某一确定有限自动机(DFA)的状态转换图如图2-2所示,与该DFA等价的正规式是( )。
admin
2017-08-31
53
问题
某一确定有限自动机(DFA)的状态转换图如图2-2所示,与该DFA等价的正规式是( )。
选项
A、10*(0|1)*
B、((0.0)*1*)*
C、1*((011)00)*
D、(1*(01*0)*)*
答案
D
解析
本题主要考察有限自动机和正规式,这个知识点也是考试中的重点和难点。
对于判断一个有限自动机与那个正规式等价,常见的方法是分析有限自动机,清楚有限自动机所表示的含义和特性,然后用排除法找到与该有限自动机等价的正规式。
对于本题,首先分析题目中给出的状态转换图,由图可知,状态q0为唯一的终态,也是初态,那么从初态到终态可以不输入然后字符,因此该有限自动机可识别空串。
另外,仔细分析有限自动机,不难发现,以一个0离开状态q0然后再以一个0返回状态q0。那么从初态到终态输入0的个数必须是偶数,而该有限自动机只能识别0和1两种字符。因此该自动机识别的串是包含偶数0的二进制代码串。
清楚了该有限自动机的特性和含义后,我们再逐个分析四个正规式。
在正规式1*0(011)*中,不能确保0的个数是偶数,而不能表示空串(因为所有闭包取空,结果仍然有一个1),因此这个正规式肯定不与有限自动机等价。
在正规式((0*0)*1木)木中,可以表示空串,但不能确保0的个数是偶数,因此也不等价于题目给出的有限自动机。
同样的道理,可知正规式1*((0|1)00)*也不与题目给出的有限自动机等价。
而在正规式(1*(01*0)*)*中,即可以表示空串,也由于(01*0)这部分不管重复多少次,都能确保0的个数是偶数,因此等价。
转载请注明原文地址:https://kaotiyun.com/show/9NRZ777K
本试题收录于:
软件设计师上午基础知识考试题库软考中级分类
0
软件设计师上午基础知识考试
软考中级
相关试题推荐
在OSI参考模型中,物理层通过物理连接在(1)之间提供比特流的传输;数据链路层通过数据链路在(2)之间提供数据链路进行服务单元透明传输;网络层通过网络连接在(3)之间交换网络服务数据单元;传输实体向(4)提供面向连接的传输服务。在应用层提供的公共应用服务元
假设用户Q1有2000台主机,则必须给他分配(1)个C类网络,如果分配给用户Q1的超网号为200.9.64.0,则指定给Q1的地址掩码为(2);假设给另一用户Q2分配的C类网络号为200.9.16.0~200.9.31.0,如果路由器收到一个目标地址为11
对于UML提供的一系列支持面向对象的分析与设计的图,(48)给出系统的静态设计视图;(49)对系统的行为进行组织和建模是非常重要的;(50)和(51)都是描述系统动态视图的交互图,其中(52)描述了以时间顺序组织的对象之间的交互活动,(53)强调收发消息的
Internet协议第4版(IPv4)为整个Internet提供了基本的通信机制,但随着应用的发展,迫切需要对IPv4进行更新,新一代的IP协议已被正式命名为IPv6。在IPv6中,每个地址有(1)个八位组,为方便网络管理人员阅读、管理,采用(2)进制加冒
ARP木马利用(1)协议设计之初没有任何验证功能这一漏洞而实施破坏。在以太网中,源主机以(2)方式向网络发送含有目的主机IP地址的ARP请求包;目的主机或另一个代表该主机的系统以(3)方式返回一个含有目的主机IP地址及其MAC地址对的应答包。源主机将这个地
下面叙述中正确的是(16)。不是进程调度时机的是(17)。多道程序系统中,当(18)时,进程从执行状态转变为就绪状态。系统中有4个并发进程,都需要某类资源3个。试问该类资源最少为(19)个时,不会因竞争该资源而发生死锁。若P/V操作的信号量S的初值为3,则
在数据的两种交换方式中,分组交换与线路交换相比,最大的优点是(238),最大的缺点是(239)。设待传送数据总长度为L位、分组长度为P位,其中头部开销长度为H位,源节点到目的节点之间的链路数为h,每个链路上的延迟时间为D秒,数据传输率为B位/秒,线路交换和
x.25分组头用于网络控制时,其长度随分组类型不同而有所不同,但至少包含前(107)。
若某计算机系统的I/O接口与主存采用统一编址,则输入输出操作是通过()指令来完成的。
以下关于cIsc(ComplexInstructionSetComputer,复杂指令集计算机)和RISC(Re-ducedInstruetionSetComputer,精简指令集计算机)的叙述中,错误的是()。
随机试题
回阳救急汤含
属于我国法定职业病的听觉系统损伤是
54岁女性.脑动脉硬化症病史3年,突感眩晕、呕吐、言语不清。查体:声音嘶哑、吞咽困难、言语含混,左眼裂小、瞳孔小、水平眼震、左面部右半身痛觉减退,左侧指鼻试验不准.诊断
A.几何均数B.四分位数间距C.中位数D.算术均数E.标准差反映一组观察值,离散程度最好的指标是
陈皮以广东新会产者佳,功效为
陆先生,72岁,因右下肢股骨颈骨折入院,给予患肢持续牵引复位。病人情绪紧张,主诉患肢疼痛。评估病人后,护士应首先解决的健康问题是
国民经济盈利能力的评价指标是()。
位于我国境内某市的一家电子产品生产企业,为增值税一般纳税人,拥有自己的核心自主知识产权,2011年至2015年经相关机构认定为高新技术企业,2014年度有关经营情况如下:(1)全年取得销售电子产品的不含税收入7000万元,取得房屋租金收入200万
我们的家是个连续性的事业社群,它的主轴是在父子之间,在婆媳之间,是纵的,不是横的。夫妇成了配轴。配轴虽则和主轴一样并不是临时性的,但是这两轴却都被事业的需要而排斥了普通的感情。我所谓普通的感情是和纪律相对照的。一切事业都不能脱离效率的考虑。求效率就得讲纪律
气管颈段(cervicalsegmenttrachea)
最新回复
(
0
)