首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
某一确定有限自动机(DFA)的状态转换图如图2-2所示,与该DFA等价的正规式是(14)。
某一确定有限自动机(DFA)的状态转换图如图2-2所示,与该DFA等价的正规式是(14)。
admin
2015-06-03
57
问题
某一确定有限自动机(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://kaotiyun.com/show/WCRZ777K
本试题收录于:
软件设计师上午基础知识考试题库软考中级分类
0
软件设计师上午基础知识考试
软考中级
相关试题推荐
国际标准化组织制定的OSI网络管理协议是(1),另外,ISO还定义了5个管理功能域,(2)属于性能管理域。LAB制定的网络管理协议是SNMP,在SNMPv2管理框架中使用的管理信息库为(3)。管理站(Manager)通过GetRequest命令查询代理(A
在下列的各选项中,(19)是Linux中一种常用的引导工具;在Linux操作系统下安装网卡,如果操作系统没有内置的驱动程序,那么用户必须(20),才能完成驱动程序的安装;为一块设备名为eth0的网卡分配中地址和子网掩码的命令是:(21);如果不打算使用DN
ATM的155Mb/s接口中,UNI使用(41)。ATM交换机是一个多端口设备,但不可以充当(42)。SMDS是基于IEEE(43)的规范,SMDS数据分组的格式包括(44)。SMDS的说法中,(45)是不妥的。
ISO9000系列标准和软件成熟度模型CMM都着眼于质量和过程管理。ISO9000系列标准的主导思想如下:(1)强调质量(4);(2)使影响产品质量的全部因素始终处于(5)状态;(3)要求证实企业具有持续提供符合要求产品的(6):
I/O系统主要有(24)、(25)和(26)三种方式来与主机交换数据。其中(24)主要用软件方法来实现,CPU的效率低;(25)要有硬件和软件两部分来实现,它利用专门的电路向CPU中的控制器发出I/O服务请求,控制器则(27)转入执行相应的服务程序;(26
下面关于几个网络管理工具的描述中,错误的是()。
结构化综合布线系统分为六个子系统,其中水平子系统的作用是(67),干线子系统的作用是(68)。(68)
李富是某公司的产品设计部的设计师,他经过努力工作,研究出了一种新的产品外形,该公司利用这一设计制造出新的产品后,致使销量大增。同时,对该设计申请了专利保护,那么其专利权应该归()所有。
随机试题
水泥的安定性一般是指水泥在凝结硬化过程中()变化的均匀性。
精美的艺术世界,是一个令人神往的奇妙世界。在这个世界中,相同时代和地域,或者不同时代和地域的作者与读者,都可以按不同的社会倾向和审美趣味,交换着对社会人生的体验,进行着心的交流。莎士比亚笔下的王子复仇,可以刺激东方的读者去思索世界的罪恶与正义;曹雪芹笔下的
婴儿维生素D缺乏性手足搐搦症最常见的临床表现是()
下列各项,属被动体位的是
不同回路、不同电压和交流与直流的导线,不得穿人同一管子内。()
孙某曾应聘在甲公司工作,试用期满后从事技术工作,2年后跳槽至乙企业成为该企业的业务骨干。甲公司为实施新的公司战略,拟聘请孙某担任公司高管。经协商,双方签订了劳动合同,约定:(1)劳动合同期限为2年,试用期为3个月;(2)合同期满或因其他原因离职后,孙某在3
()用来解释相似资源储备国家之间和同类工业品之间的双向贸易现象。
经济全球化是当今世界经济发展的重要趋势,其明显表现有
在面向对象方法中,类的实例称为______。
ParticipantsintheShanghaiCo-operationForum______regionalteamworktopromoteinvestmentandeconomicdevelopment.
最新回复
(
0
)