首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
图2-3所示为一确定有限自动机的状态转换图,图中的(15)是可以合并的状态。
图2-3所示为一确定有限自动机的状态转换图,图中的(15)是可以合并的状态。
admin
2015-06-03
52
问题
图2-3所示为一确定有限自动机的状态转换图,图中的(15)是可以合并的状态。
选项
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后,状态O转换为状态1,而状态1转换为状态2。因此{1}和{2}中的状态是可区别的。
由于状态2,3输入字符a得到相同的结果3,输入字符b得到相同结果2,所以子集{2,3}是不可区别的。从而得到新的划分:({0},{1},{2,3}),因此,本题的正确答案为B。
转载请注明原文地址:https://kaotiyun.com/show/XCRZ777K
本试题收录于:
软件设计师上午基础知识考试题库软考中级分类
0
软件设计师上午基础知识考试
软考中级
相关试题推荐
网络管理协议中,简单网络管理协议SNMP是(1)协议,它基于(2)协议来传输数据。SNMP提供了4类管理操作,其中(3)操作用来提取特定的网络管理信息。SNMP是通过(4)方式实现管理功能的。在SNMP管理控制框架中定义了管理进程和管理代理,其中网络管理工
MODEM是一种DCE,计算机是一种DTE,根据接口标准RS-232,MODEM和计算机之间至少需要连接的线数是(293)。MODEM收到呼叫信号后向计算机发送的信号是(294)。当数据发送完毕,计算机向MODEM发送的信号是清除(295)、MODEM随后
ATM的155Mb/s接口中,UNI使用(41)。ATM交换机是一个多端口设备,但不可以充当(42)。SMDS是基于IEEE(43)的规范,SMDS数据分组的格式包括(44)。SMDS的说法中,(45)是不妥的。
下面叙述中正确的是(16)。不是进程调度时机的是(17)。多道程序系统中,当(18)时,进程从执行状态转变为就绪状态。系统中有4个并发进程,都需要某类资源3个。试问该类资源最少为(19)个时,不会因竞争该资源而发生死锁。若P/V操作的信号量S的初值为3,则
系统测试是将软件系统与硬件、外设和网络等其他因素结合,对整个软件系统进行测试,目的是为了发现系统不符合用户需求的部分。(4)不是系统测试的内容。
系统测试是将软件系统与硬件、外设和网络等其他因素结合起来,进行信息系统的各种组装测试和确认测试,(55)不是系统测试的内容。
建筑物综合布线系统中工作区子系统是指__________。(2011年下半年试题)
建筑物综合布线系统中的干线子系统是(66),水平子系统是(67)。(67)
下列智力成果中,能取得专利权的是()。
如果两名以上的申请人分别就同样的发明创造申请专利,专利权应授予(10)。
随机试题
根据《药品说明书和标签管理规定》,关于药品标签上药品有效期的规定的说法,错误的是
“启发”和“举一反三"都出自__________一书。
慢性消化性溃疡的发生与下列因素无关的是
胰腺主胰管直径
温燥伤肺,气阴两伤证,治宜选用()
患者,女性,29岁,未婚。近期由于工作劳累紧张,心悸、多汗2个月余。查体:甲状腺Ⅱ度肿大,有血管杂音,心率130/分,FT3、FT4升高,TSH显著降低,首选治疗方案为
对已昏迷的急性中毒患者不宜洗胃。()
对仪器设备进行符合性确认评定时,如果评定值误差的不确定度与被评定仪器设备的最大允许误差的绝对值之比()1:3,则可以不考虑测量不确定度影响。
()的登记是社区人群健康相关资料调查中最关键的项目。
提倡劳动教育的教育思想家是()
最新回复
(
0
)