首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
图2-3所示为一确定有限自动机的状态转换图,图中的( )是可以合并的状态。
图2-3所示为一确定有限自动机的状态转换图,图中的( )是可以合并的状态。
admin
2019-06-12
28
问题
图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
软件设计师上午基础知识考试
软考中级
相关试题推荐
以下关于网络工程需求分析的叙述中,错误的是()。
在TCP/IP协议配置好以后,ipconfig命令显示结构不包括下列__________。
下面的说法不正确的是_________。
在Linux操作系统中,命令()可以正确关闭系统防火墙。
以下关于三重DES加密的叙述中,正确的是(41)________________。
DNS服务器在名称解析过程中正确的查询顺序为______。
下面的光纤以太网标准中,支持1000m以上传输距离的是____________。
WindowsServer2003采用IPSec进行保密通信,如果密钥交换采用“主密钥完全向前保密(PFS)”,则“身份验证和生成密钥间隔”默认值为480分钟和(33)个会话。
阅读以下说明和C++代码,将应填入(n)处。[说明]在一公文处理系统中,开发者定义了一个公文类OfficeDoc,其中定义了公文具有的属性和处理公文的相应方法。当公文的内容或状态发生变化时,关注此OfficeDoc类对象的相应的DocExplor
阅读下列说明和C代码,回答以下问题,将解答写在答题纸的对应栏内。【说明】用两台处理机A和B处理n个作业。设A和B处理第i个作业的时间分别为ai和bi。由于各个作业的特点和机器性能的关系,对某些作业,在A上处理时间长,而对某些作业在B上处理时间
随机试题
设备安装过程的质量控制主要包括()等不同工序的质量控制。
在测定基础代谢率的注意事项中,错误的是
A.在100℃5min灭活的病毒B.煮沸10min灭活的肝炎病毒C.60℃10h灭活的肝炎病毒D.-20℃可保持10d的肝炎病毒E.紫外线可以杀灭所有的肝炎病毒乙型肝炎病毒
机电工程项目采购的程序中,一般应在召开厂商协调会后进行的工作是( )。
以“君子和而不同”为题即兴演讲。
英语目前是世界上不同语言群体之间进行交流的主要方式,这种交流是文化间的知识交流,它的_______是存在着相互分离的文化。换句话说,作为通用语言的英语是处理语言差异和文化差异的方式,而不是_______它们的方式。填入划横线部分最恰当的一
奥运会田径比赛男子10000米的决赛中,始终跑在最前面的甲、乙、丙三人中,一个是美国选手,一个是埃塞俄比亚选手,一个是肯尼亚选手,比赛结束后得知:
对于以放火的危险方法实施破坏交通工具的行为,应当()
【F1】Thevaluewhichsocietyplacesonworkhastraditionallybeencloselyassociatedwiththevalueofindividualismandasare
WanttoKnowYourDiseaseRisk?CheckYourExposomeA)Whenitcomestohealth,whichismoreimportant,natureornurture?Youm
最新回复
(
0
)