首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
对于下图的DFAM进行化简,与其等价的最少状态的DFAM’是(27)。
对于下图的DFAM进行化简,与其等价的最少状态的DFAM’是(27)。
admin
2009-02-15
25
问题
对于下图的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)才能使接收方知道如何处理。
IETF定义的多协议标记交换(MPLS)是一种第3层交换技术,MPLS网络由(38)组成,负责为网络流添加删除标记的是(39)。
容量为64块的Cache采用组相联方式映像,字块大小为128个字,每4块为一组。若主存容量为4096块,且以字编址,那么主存地址应为(7)位,主存区号应为(8)位。
基于ISOOSI/RM模型的(38)是一个完整的网络管理协议族,其网络管理应用进程使用OSI参考模型的应用层。
假定由网络管理站向代理发送如下命令: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)因为对
OSI网络管理标准定义了网管的5大功能。比如对每一个被管理对象的每一个属性设置阈值、控制阈值检查和告警的功能属于(51);接收报警信息、启动报警程序、以各种形式发出警报的功能属于(52);接收告警事件、分析相关信息、及时发现正在进行的攻击和可疑迹象的功能属
题1:网络协议是计算机网络和分布系统中互相通信的(21)间交换信息时必须遵守的规则的集合。协议的关键成分中(22)是数据和控制信息的结构或格式;(23)是用于协调和进行差错处理的控制信息;定时是对事件实现顺序的详细说明,而网络体系结构则是(24)。
知识产权分为工业产权和(54),由于智力成果具有可以同时被多个主体所使用的特点,因此法律授予知识产权这种专有权具有(55),知识产权具有法定的保护期限,而商业秘密受法律保护的期限为(56),甲A未经乙B的同意擅自发表B的软件产品,甲A这种行为构成(57),
在面向对象分析过程中,用概念模型来详细描述系统的问题域,用(5)来表示概念模型。(6)关系用于表示类与类、接口与接口之间的继承关系;在Java中,用(7)关键字来直接表示这种关系。
在软件的生命周期中,下列说法错误的是(37)。
随机试题
主要特征为领导者大权独揽,小权分散的领导决策方式是()
下列会计科目中,属于流动负债的是()。
A、Anopeningspeechofalecture.B、Thetextoftheeconomist’sspeech.C、Adiscussiononinflationandinvestment.D、Theinterp
下列关于癌基因的说法正确的是
项目盈亏平衡分析中,若其他条件不变,可以降低盈亏平衡点产量的途径有()。
小马大学毕业后应聘到红叶机械集团公司工作已2年。最近,集团公司决定对主营业务进行调整,小马所在的部门将被撤并。公司领导找小马谈话,提出了两个建议,一是公司新设立了劳务派遣公司,建议小马将与公司建立的劳动关系转到劳务派遭公司,由该劳务派遣公司将小马再派遣到集
充分发挥主观能动性,人们就能突破历史条件所许可的范围,开拓新的局面。()
①《禹贡》主要以山脉、河流和海洋为自然分界,把所描述的地区分为九州,不受当时诸侯割据形势的局限,把广大地区作为一个整体来研究,分别阐述九州的山川、湖泽、土壤、物产等,是自然区划思想的萌芽②此后,主要论述疆域、政区建制沿革的著作不断涌现,除正史有地理志外,
人们谈到要培养儿童成才,首先考虑的是如何提高他们的智力、如何提高他们的学习成绩。似乎成绩好的孩子将来就有出息。其实,这种看法是不全面的。不少研究资料表明,世界上有名的科学家、企业家、社会活动家,其成功的因素中,智力因素才占了三分之二。这段话主要支持的观点是
Everyprofessionortrade,everyart,andeverysciencehasitsowntechnicalvocabulary.The【C1】______ofthesetechnicalvocab
最新回复
(
0
)