首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
图2-3所示为一确定有限自动机的状态转换图,图中的(15)是可以合并的状态。
图2-3所示为一确定有限自动机的状态转换图,图中的(15)是可以合并的状态。
admin
2015-06-03
53
问题
图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
软件设计师上午基础知识考试
软考中级
相关试题推荐
在TCP/IP网络中,主机A和主机B通过一路由器互联,提供两主机应用层之间通信的层是(248),提供机器之间通信的层是(249),具有IP层和网络接口层的设备是(250);在A与路由器和路由器与B使用不同物理网络的情况下,主机A和路由器之间传送的数据帧与路
用于所有网络设备的完整网络管理协议族是(1),它的整体结构建立在(2)参考模型的基础上。网络管理应用进程使用该参考模型中的(3)。在该层上,公共管理信息服务单元(CMISE)提供了应用程序使用(4)协议的接口。SNMP是应用最广泛的网络管理协议,其最新版本
Internet是由众多网络互联而成的计算机网络,狭义Internet是指由那些采用IP协议的网络互联而成的网络,广义Internet是指狭义Internet加上所有(332)的网络。Internet体系结构具有良好扩充性的主要原因在于它(333)。广义I
对一路信号的载波频率为f0,进行FSK调制后的信号频率分别为f1和f2(f1<f2),则三者的关系是(298)。当对多路信号进行调制时,调制后各信号的频谱(299)。信号到达接收端后通过(300)分离各路信号。WDM与FDM工作方式相似,但WDM调制的是(
ISO9000系列标准和软件成熟度模型CMM都着眼于质量和过程管理。ISO9000系列标准的主导思想如下:(1)强调质量(4);(2)使影响产品质量的全部因素始终处于(5)状态;(3)要求证实企业具有持续提供符合要求产品的(6):
某CPU的主振频率为100 MHz,平均每个机器周期包含4个主振周期。各类指令的平均机器周期数和使用频度如表2.9所示,则该计算机系统的速度为平均约(5)兆指令/秒。若某项事务处理工作所要执行的机器指令数是控制程序(以访内、比较与转移等其他指令为主)220
X、Y为逻辑变量,与逻辑表达式等价的是__________。(2012年下半年试题)
建筑物综合布线系统中的工作区子系统是指()。
阅读以下预备知识、函数说明和C代码,将应填入(n)处的字句写在对应栏内。[预备知识]①对给定的字符集合及相应的权值,采用哈夫曼算法构造最优二叉树,并用结构数组存储最优二叉树。例如,给定字符集合{a,b,c,d}及其权值2、7、4、5,可构造如图
随机试题
在Windows中,“开始”菜单“文档”选项中的文件可以是文本文件、Word文件,也可以是BMP文件或其他文件。()
肝性脑病患者禁用的灌肠液是
色甘酸钠抗变态反应的作用机制是
男性,44岁,有咳嗽、咳痰史5年,伴喘息,入院前3天因受寒咳嗽、喘加重,咳黄痰入院。入院时查体,桶状胸,叩诊过清音,肺肝浊音界右锁骨中线第7肋间,双肺干、湿性哕音及散在哮鸣音,肺功能:FEV1/FVC为56%,MVV60%,VC降低,RV/TLC为43%。
当感抗小于容抗时,则电压滞后电流,电路呈( )。
按CIF术语成交的合同,货物在运输途中因火灾被焚,应由()。
下列关于公积金个人住房贷款业务的职责分工的表述,正确的有()。
()已经成为了现代社会保障的核心内容。
新航路开辟后,导致欧洲封建主收入下降的原因是()。
Ifartseekstodivorceitselffrommeaningfulandassociativeimages,ifitholdsmaterialaloneasitsobjective,thenIthink
最新回复
(
0
)