首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
对于下图的DFAM进行化简,与其等价的最少状态的DFAM’是(27)。
对于下图的DFAM进行化简,与其等价的最少状态的DFAM’是(27)。
admin
2009-02-15
73
问题
对于下图的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)才能使接收方知道如何处理。
在缺省配置的情况下,交换机的所有端口(59)。连接在不同交换机上的、属于同一VLAN的数据帧必须通过(60)传输。
基于ISOOSI/RM模型的(38)是一个完整的网络管理协议族,其网络管理应用进程使用OSI参考模型的应用层。
基于Kerberos协议的身份认证系统利用智能卡产生一次性密钥,可以防止窃听者捕获认证信息;为了防止重发攻击(Replayattack),在报文中加入了(31)。
OSI网络管理标准定义了网管的5大功能。比如对每一个被管理对象的每一个属性设置阈值、控制阈值检查和告警的功能属于(51);接收报警信息、启动报警程序、以各种形式发出警报的功能属于(52);接收告警事件、分析相关信息、及时发现正在进行的攻击和可疑迹象的功能属
对照ISO/OSI参考模型各个层中的网络安全服务,在物理层可以采用(26)加强通信线路的安全;在数据链路层,可以采用(27)进行链路加密;在网络层可以采用(28)来处理信息内外网络边界流动和建立透明的安全加密信道;在传输层主要解决进程到进程间的加密,最常见
信元是信元交换的单位。为控制差错,在信元中包括CRC校验和,其生成公式为(6),校验和对(7)进行校验。信元交换采用(8)技术进行复用。在交换过程中,当实施VP交换时,其中VPI、VCI的变化情况是(9)。若在交换过程中出现拥塞,该信息被记录在信元的(10
Inlow-speednetwork,itisusuallyadequatetowaitforcongestiontooccurandthenreacttoitbytellingthesourceofpacke
CMM(软件能力成熟度模型)描述和分析了软件过程能力的发展与改进的程度,确立了一个软件过程成熟程度的分级标准。在初始级,软件过程定义几乎处于无章可循的状态,软件产品的成功往往依赖于个人的努力和机遇;在(44),已建立了基本的项目管理过程,可对成本、进度和功
对欲访问特定信息的发起者的身份或者对传送的报文完整性进行合法性审查或核实的行为称为(50)。在日常生活中,我们可以用手写签名来防止否认的发生。在计算机通信中,要解决这类问题,可采用的方法是(51)。关于客户/服务器应用模式,说法正确的是(52)。在理论上,
随机试题
word2010中,“形状”工具在()选项卡。
Shebelievesancientcluesburiedunderwatercansavelives,particularlyinplaceswithoutwrittenrecords.
社会主义现代化建设中,人民政协的基本职能是()。
钢一混凝土结合梁混凝土桥面应全断面连续浇筑,以下浇筑顺序正确的是()。
方格理论认为最理想的领导风格是()。
根据《植物新品种保护条例》及相关规定,对于植物新品种申请需要初步审查哪些内容?
根据我国青年、少年、儿童工作在体制上的划分,各地妇联组织中的儿童工作部门负责的工作对象的年龄段在( )岁。
下图在篮球运动中属于()战术。
我国刑法规定的量刑制度不包括()。
《横滨每日新闻》
最新回复
(
0
)