首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
对于下图的DFAM进行化简,与其等价的最少状态的DFAM’是(27)。
对于下图的DFAM进行化简,与其等价的最少状态的DFAM’是(27)。
admin
2009-02-15
85
问题
对于下图的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
软件设计师上午基础知识考试
软考中级
相关试题推荐
IETF定义的多协议标记交换(MPLS)是一种第3层交换技术,MPLS网络由(38)组成,负责为网络流添加删除标记的是(39)。
容量为64块的Cache采用组相联方式映像,字块大小为128个字,每4块为一组。若主存容量为4096块,且以字编址,那么主存地址应为(7)位,主存区号应为(8)位。
光缆布线系统的测试是工程验收的必要步骤。以下不是对光缆进行测试的工作内容的是(57)。
WindowsServer2003操作系统中,域用户信息存储于(34)中。(35)不属于WindowsServer2003活动目录的物理结构。
OSI网络管理标准定义了网管的5大功能。比如对每一个被管理对象的每一个属性设置阈值、控制阈值检查和告警的功能属于(51);接收报警信息、启动报警程序、以各种形式发出警报的功能属于(52);接收告警事件、分析相关信息、及时发现正在进行的攻击和可疑迹象的功能属
Inlow-speednetwork,itisusuallyadequatetowaitforcongestiontooccurandthenreacttoitbytellingthesourceofpacke
为了检测系统是否有木马侵入,可以使用Windows操作系统的(53)命令查看当前的活动连接端口。
在OSI网络管理标准中定义了网络管理的5大功能。对历史数据进行分析、统计和整理,为未来的网络规划提供参考的功能属于(41);提供一系列实时数据采集、分析和可视化工具对流程、负载、丢包、温度、内存、延迟等网络设备和线路进行实时检测的功能属于(42);接收报警
WhiletheInternetisinherentlyinsecure,businessesstillneedtopreservetheprivacyofdataasittravelsoverthenetwork.
阅读以下说明,回答下面问题。【说明】ADSL是接入Internet的一种宽带技术。下图1.9为一台带网卡的PC机采用ADSL接入Internet的网络结构图。
随机试题
简述遵义会议的主要内容。
A.阴道镜下宫颈活组织检查B.筋膜外全子宫切除C.动脉插管化疗后放疗D.广泛性全子宫切除术,盆腔淋巴结清扫术E.放疗37岁。接触性出血史,宫颈重度糜烂。刮片巴氏Ⅲ级,应进行
麻疹的病变部位在水痘的病变部位在
治疗病毒性脑炎错误的方法是
宏观经济管理的首要任务是()。
小王于2005年5月16日买入某附息债券,包含应计利息3.49元在内共支付92.54元。该债券面值100元,票面利率8%,每年付息两次,计息基础为实际天数,到期日为2010年6月8日,则债券的到期收益率为()。
根据土地增值税法律制度的规定,纳税人在计算房地产开发费用时,财务费用中的借款利息支出,凡能够按照转让房地产项目计算分摊并提供金融机构证明的,允许据实扣除。但不能计入利息支出扣除的有()。
叶酸只有还原成二氢叶酸才能发挥其生理活性。()
Java语言中提供了【】来管理组件在容器中的布局。
下列程序的功能是:当发生窗体的单击事件后,将在窗体上显示“1!+2!+3!+…+10!”的和。PrivateSubForm_Click()DimsAsLong,iAsIntegers=0Fori=1
最新回复
(
0
)