首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
对于下图的DFAM进行化简,与其等价的最少状态的DFAM’是(27)。
对于下图的DFAM进行化简,与其等价的最少状态的DFAM’是(27)。
admin
2009-02-15
70
问题
对于下图的DFAM进行化简,与其等价的最少状态的DFAM’是(27)。
选项
A、
B、
C、
D、
答案
D
解析
所谓一个DFA M=(∑,Q,q0,F,δ)的化简是指寻找一个状态数比较少的DFA M’,使L(M)=L(M’),而且可以证明存在一个最少状态的DFAM’,使L(M’)=L(M)。
下面介绍最少状态的DFA和等价状态,最少状态DFA必须满足以下两个条件。
(1)没有多余状态(死状态):多余状态是指从该自动机的开始状态出发,任何输入串都不能到达的那些状态。
(2)没有两个状态是互相等价(不可区别)的。
设p,q∈Q。若对任何w∈∑*,δ(p,w)∈F当且仅当δ(q,w)∈F,则称状态p和q是等价的。如果p和q不等价,则称p,q是可区别的。
DFA M的最小化过程是把M的状态集Q分割成一些互不相交的子集,使得每个子集中任何两个状态是等价的,而任何两个属于不同子集的状态都是可区别的。然后在每个子集中任取一个状态做“代表”,而删去子集中其余状态,并把指向其余状态集的箭弧都改作指向这个做“代表”的状态集中。这样得到的状态转换图所对应的DFA M’就是接受L(M)的具有最少状态的DFA。
两个状态s和t如果同时满足下列两个条件,就称s和t是等价的。
(1)一致性:同是终态或同是非终态。
(2)蔓延性:
a∈∑, δ(s,a)=q,δ(t,a)=q’,q,q’等价。
本题的简化过程如下:首先,将图中状态分为终态和非终态两个子集即({0,2,4}、{1,3}),再进行子集划分,观察第1个子集{0,2,4},输入。后,状态0转换为状态2,状态2转换为状态2,状态4转换为状态4,输入1后,{0,2,4}中的状态转换到{1,3}。因此子集{0,2,4}不可分割。观察第2个子集{1,3},输入0后,状态1、3转换到状态3;输入1后,状态1、 3转换到状态4。因此子集{1,3}也是不可分割的。
重复子集划分步骤,发现状态集无法划分。在子集{0,2,4}中选择0状态作为代表,在子集{1,3}中选择1状态作为代表,画出最少状态的DFA是被选答案中的D。
转载请注明原文地址:https://kaotiyun.com/show/VRxZ777K
本试题收录于:
软件设计师上午基础知识考试题库软考中级分类
0
软件设计师上午基础知识考试
软考中级
相关试题推荐
在层次网络体系结构中,第n层协议利用(2)提供的服务向(3)提供服务,对等实体是指(4),数据在同一个系统自上层传到下层,这种数据格式称为(5),某层实体接收到上层传来的数据后,一般要(6)才能使接收方知道如何处理。
现代计算机体系结构的发展突破了冯.诺依曼的体系结构,主要表现在(61)。多机系统与多计算机构成的计算机网络差别的主要特征是(62)。面向对象程序设计以(63)为基本的逻辑构件,用(64)来描述具有共同特征的一组对象,以(65)为共享机制,共享类中的方法和数
假定由网络管理站向代理发送如下命令:SetRequest(ipRouteDest.10.1.2.3=10.1.2.3,ipRouteMetric.10.1.2.3=2,ipRouteNextHop.10.1.2.3=10.5.4.3)因为对
下面关于以太网交换机部署方式的描述中,说法错误的是(59)。
MostIPlayer-basedproxymechanisms,suchasnetworkaddresstranslation(NAT),onlysupportuni-directionalproxy,fromtheint
知识产权分为工业产权和(54),由于智力成果具有可以同时被多个主体所使用的特点,因此法律授予知识产权这种专有权具有(55),知识产权具有法定的保护期限,而商业秘密受法律保护的期限为(56),甲A未经乙B的同意擅自发表B的软件产品,甲A这种行为构成(57),
HTTP协议是常用的应用层协议,它通过(22)协议提供服务,上下层协议默认时,使用(23)端口进行服务识别。HTTP双方的一次会话与上次会话是(24),即协议是无状态的。从交换信息的整体性说是(25),SHTTP对HTTP的扩展在于(26)。
WhiletheInternetisinherentlyinsecure,businessesstillneedtopreservetheprivacyofdataasittravelsoverthenetwork.
CMM(软件能力成熟度模型)描述和分析了软件过程能力的发展与改进的程度,确立了一个软件过程成熟程度的分级标准。在初始级,软件过程定义几乎处于无章可循的状态,软件产品的成功往往依赖于个人的努力和机遇;在(44),已建立了基本的项目管理过程,可对成本、进度和功
对欲访问特定信息的发起者的身份或者对传送的报文完整性进行合法性审查或核实的行为称为(50)。在日常生活中,我们可以用手写签名来防止否认的发生。在计算机通信中,要解决这类问题,可采用的方法是(51)。关于客户/服务器应用模式,说法正确的是(52)。在理论上,
随机试题
A.胸骨左缘B.胸骨右缘C.心尖内侧D.心前区听诊开瓣音最清楚的部位是
某猪场2岁种公猪,精神沉郁,步态强拘,拱背,腰部触诊敏感,常做排尿姿势。尿检可见红细胞、白细胞、盐类结晶、肾上皮细胞。该病可能的诊断是()
A.表寒里热证B.表热里寒证C.上寒下热证D.上热下寒证E.真热假寒证下利清谷,小便清长,舌淡苔白,面赤口渴多见于
总监理工程师负责项目监理机构内所有监理人员利益的分配。这表明,总监理工程师是项目监理的()。
关于混凝土或抹灰基层雨期涂刷涂料的基层含水率说法,正确的是()。
会计机构和会计人员应当按照国家统一的会计制度的规定对原始凭证进行认真审核,对记载不准确、不完整的原始凭证()。
鲁迅在上海期间的创作主要是()文体。
计算机系统中,【】通常用8位二进制组成,可代表一个数字、一个字母或一个特殊符号。
关于因特网的域名系统,以下哪种说法是错误的?______。
BlowingHotandColdClimatechangemaybeslowanduncertain,butthatisnoexcuseforinaction.Onereasonwhyuncertaint
最新回复
(
0
)