首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
图2-3所示为一确定有限自动机的状态转换图,图中的( )是可以合并的状态。
图2-3所示为一确定有限自动机的状态转换图,图中的( )是可以合并的状态。
admin
2019-06-12
21
问题
图2-3所示为一确定有限自动机的状态转换图,图中的( )是可以合并的状态。
选项
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后,状态0转换为状态1,而状态1转换为状态2。因此{1}和{2}中的状态是可区别的。
由于状态2,3输入字符a得到相同的结果3,输入字符b得到相同结果2,所以子集{2,3}是不可区别的。从而得到新的划分:({0},{1),{2,3}),因此,本题的正确答案为B。
转载请注明原文地址:https://kaotiyun.com/show/uoCZ777K
本试题收录于:
软件设计师上午基础知识考试题库软考中级分类
0
软件设计师上午基础知识考试
软考中级
相关试题推荐
<title style="italic">science</title>是一个XML元素的定义,其中元素标记的属性值是(65)。
可以用数字信号对模拟载波的不同参量进行调制,图1-3所示的调制方式称为______。
设信号的波特率为500Baud,采用幅度.相位复合调制技术,由4种幅度和8种相位组成16种码元,则信道的数据速率为___________。
在进行域名解析过程中,由______获取的解析结果耗时最短。
快速以太网标准100Base-TX规定的传输介质是__________。(2011年上半年试题)
SMTP协议用于(36)电子邮件。
以下用于在网络应用层和传输层之间提供加密方案的协议是(36)。
以下关于在IPv6中任意播地址的叙述中,错误的是_____________。
(1)请说明流程图1中的文件F0、F1分别是哪个文件。(2)处理1和处理5分别按照哪些数据项进行分类?处理4能发现哪些错误(不需考虑设备故障错误)?
在文件存储设备管理中,有三类常用的空闲块管理方法,即位图向量法,空闲块链表连接法和______。
随机试题
A.五味子B.小茴香C.女贞子D.枸杞子E.栀子来源于木犀科,表面黑紫色或灰黑色的药材是()。
A非那雄胺B醋酸泼尼松龙C醋酸甲羟孕酮D甲睾酮E达那唑甾核2,3一与异嗯唑拼合的药物,用于治疗子宫内膜异位症
代谢蔗糖能力最强的细菌是
在现代化社会中,“处方调剂”仍然是药师实施药学服务的
因房屋不具备所有权转移登记条件而导致交易终止,买方已存入监管专用账户的资金应()。
FIDIC合同条件规定的“暂列金额”特点之一是()。
下列会计处理方法中,符合权责发生制基础的是()。
成年人杨某对5岁的小明说:“你敢砸人家的玻璃,你就是英雄。”小明听后,拿起一块石头就砸破了小刚家的玻璃。对小刚家的损失应承担赔偿责任的是()。
设随机变量X~N(μ,σ2),则P(|X一μ|<2σ)().
关于性能管理的描述中,正确的是()。
最新回复
(
0
)