首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
图2-3所示为一确定有限自动机的状态转换图,图中的( )是可以合并的状态。
图2-3所示为一确定有限自动机的状态转换图,图中的( )是可以合并的状态。
admin
2019-06-12
27
问题
图2-3所示为一确定有限自动机的状态转换图,图中的( )是可以合并的状态。
选项
A、0和1
B、2和3
C、1和2
D、0和3
答案
B
解析
在状态转换图中,每一个结点代表一个状态,其中双圈是终结状态。该题实际上是一个简化确定有限自动机(DFA)的过程,一个确定有限自动机可以通过消除多余状态和合并等价状态而转换成一个最小的与之等价的有限自动机。
先介绍两个概念:最小状态DFA和等价状态。
最小状态DFA必须满足以下两个条件。
(1)没有多余状态(死状态):多余状态是指从该自动机的开始状态出发,任何输入串都不能到达的那个状态。
(2)没有两个状态是互相等价(不可区别)。
两个状态s和t如果同时满足下列两个条件,我们就称s和t是等价的:
(1)一致性:同是终态或同是非终态。
(2)蔓延性:从s出发读入某个a和从t出发读入某个a到达的状态等价。
本题的简化过程如下:
首先,将图中状态分为终态和非终态两个子集即({0,1),{2,3}),再进行子集划分。观察第一个子集{0,1},输入b后,状态0转换为状态1,而状态1转换为状态2。因此{1}和{2}中的状态是可区别的。
由于状态2,3输入字符a得到相同的结果3,输入字符b得到相同结果2,所以子集{2,3}是不可区别的。从而得到新的划分:({0},{1),{2,3}),因此,本题的正确答案为B。
转载请注明原文地址:https://kaotiyun.com/show/uoCZ777K
本试题收录于:
软件设计师上午基础知识考试题库软考中级分类
0
软件设计师上午基础知识考试
软考中级
相关试题推荐
运行OSPF协议的路由器用(20)报文来建立和更新它的拓扑数据库。
下面的说法不正确的是_________。
位于CPU与主存之间的高速缓冲存储器(Cache)用于存放部分主存数据的副本,主存地址与Cache地址之间的转换工作由____________完成。
在进行域名解析过程中,由______获取的解析结果耗时最短。
下列关于软件著作权中翻译权的叙述不正确的是:翻译权是指______的权利。
在Linux操作系统中,命令()可以正确关闭系统防火墙。
中国企业M与美国公司L进行技术合作,合同约定M使用一项在有效期内的美国专利,但该项美国专利未在中国和其他国家提出申请。对于M销售依照该专利生产的产品,以下叙述正确的是__________。(2012年上半年试题)
根据上述说明,请给出(1)“职员”关系模式的主键和外键。(2)“部门”关系模式的主键和外键。(1)用SQL定义“职员”关系模式,请在空缺处填入正确的内容。CreateTable职员(职员号CHAR(5)(a),
阅读以下说明和C++代码,将应填入(n)处。[说明]在一公文处理系统中,开发者定义了一个公文类OfficeDoc,其中定义了公文具有的属性和处理公文的相应方法。当公文的内容或状态发生变化时,关注此OfficeDoc类对象的相应的DocExplor
网络计划图由(51)组成,如果某工序的工期为0,则表示(52)。在非确定型网络计划图中,工期不是确定数,一般需估计三个数值:乐观估计时间a,最可能估计时间m,悲观估计时间不。如假定m与a的加权平均值为(a+2m)/3,m与b的加权平均值为(2m+ b)/3
随机试题
铰孔、磨孔、拉孔和研磨孔一般作为孔的精加工。()
试述急性坏死性胰腺炎的处理原则。
关于官腔粘连,下列不正确的是
莱菔子的功效特点是
不是影响抗原抗体反应的因素是
关于CT值的叙述,正确的是
2007年,广州《新快报》4名记者在麦当劳、肯德基和必胜客卧底2个月,收集了三大洋快餐非法用工的相关证据。在其举报后,广东省总工会进行了相应调查并证实:麦当劳兼职工资为4元/小时,肯德基兼职工资为4.7元/小时,必胜客兼职工资为5.8元/小时,低于当年广州
外国合作者应在合作企业的亏损弥补之后,才能先行回收投资。()
甲公司采用先进先出法计算发出存货成本。4月份库存产品数量为50件,单价为1000元;4月10日购入产品100件,单价为1050元;4月12日领用产品100件。如果甲公司本月未发生其他购货或领货业务,4月份发出产品总成本为()元。
根据《税收征收管理法》的规定,税务机关可以采取的税款征收措施不包括()。
最新回复
(
0
)