首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
对于下图的DFAM进行化简,与其等价的最少状态的DFAM’是(27)。
对于下图的DFAM进行化简,与其等价的最少状态的DFAM’是(27)。
admin
2009-02-15
83
问题
对于下图的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
软件设计师上午基础知识考试
软考中级
相关试题推荐
内存按字节编址,地址从A4000H到CBFFFH,共有(1)B。若用存储容量为16K×8bit的存储器芯片构成该内存,至少需要(2)片。
在ISO/OSI参考模型的数据链路层中,对链路进行加密采用的措施是(33)。
FDDI采用(27)方案避免环网中的时钟偏移,并规定进入站点缓冲器的数据时钟由输入信号的时钟确定,缓冲器的输出时钟信号由本站的时钟确定。
Linux系统的路由配置中,若设置静态路由,则需要(51)命令。在使用该命令时为了防止出现错误,可以用网络名字代替网络号,而网络名字可以在文件(52)中定义。为了将手工配置的命令存储下来,在系统启动时自动执行,可以通过(53)来实现。若运行动态路由,则(5
SNMPv2增加了一个非原子的Get命令,可以做到(46),SNMPv2增加的 Inform命令使得网络管理的结构可以是(47)。SNMPv1的报文中除版本号和SNMP PDU外,还包括(48),在SNMPv2中在原PDU的基础上增加了(49)信息。 RM
RS-232标准在初期可以满足人们的要求,但当人们要求以更高的速率传送到更远的距离时,需要有新的标准,RS-449就可以实现这个目的。它的标准规格中,RS-422标准是平衡式的,传输一个信号用两条线,逻辑信号的表示用(6),双线传输的好处是(7)。 X.2
文件系统采用多重索引结构搜索文件内容。设块长为512字节,每个块号长3字节,如果不考虑逻辑块号在物理块中所占的位置,那么三级索引时可寻址的文件最大长度为(3)。
信元是信元交换的单位。为控制差错,在信元中包括CRC校验和,其生成公式为(6),校验和对(7)进行校验。信元交换采用(8)技术进行复用。在交换过程中,当实施VP交换时,其中VPI、VCI的变化情况是(9)。若在交换过程中出现拥塞,该信息被记录在信元的(10
SNMPv2表的状态列有6种取值,以下哪个选项不是响应管理站的查询而返回的状态?(43)
对欲访问特定信息的发起者的身份或者对传送的报文完整性进行合法性审查或核实的行为称为(50)。在日常生活中,我们可以用手写签名来防止否认的发生。在计算机通信中,要解决这类问题,可采用的方法是(51)。关于客户/服务器应用模式,说法正确的是(52)。在理论上,
随机试题
现存的计算机平台中,哪些系统目前还没有发现被病毒感染_______
阅读下面的文字,回答问题作为思想者的巴金祝勇公元2005年10月17日,巴金走完了他101年的人生之路,不仅他的
Friendsplayanimportantpartinourlives,andalthoughwemaytakefriendshipforgranted,weoftendon’tclearlyunderstand
工程变更总费用增加或减少总共超过“有效合同价格”的()时,应在合同价格上加上或扣除一笔调整金额。
已知甲公司按平均市场价值计量的目标债务权益比为0.8,公司资本成本为10.5%,公司所得税税率为35%。如果该公司的权益资本成本为15%,则该公司税前债务资本成本为()。
______年柏辽兹完成了他一生中最重要的作品______。()
在与领导相处过程中,难免会说错话,办错事,轻则造成领导者不悦,重则造成工作上的损失。你若遇到这一情况。该怎么处理?
甲与乙是一对夫妻,许兵是甲与乙。1978年从福利院收养的男孩,许晶是甲的亲生女儿。长大后,许兵和许晶情投意合,均已达到法定婚龄,遂准备结婚。下列说法中正确的是()。
某研究设计院向不同岗位级别职工支付的工资额以及该院职工人员结构资料分别如图1和图2。根据材料回答问题。下列岗位中,报告期职工人数较基期变化幅度最小的是:
地道翻译
最新回复
(
0
)