首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
如图3-1所示为一确定有限自动机(DFA)的状态转换图,与该自动机等价的正规表达式是(1),图中的(2)是可以合并的状态。
如图3-1所示为一确定有限自动机(DFA)的状态转换图,与该自动机等价的正规表达式是(1),图中的(2)是可以合并的状态。
admin
2005-03-15
127
问题
如图3-1所示为一确定有限自动机(DFA)的状态转换图,与该自动机等价的正规表达式是(1),图中的(2)是可以合并的状态。
选项
A、(a|b)* bb(a*b*)*
B、(a|b)*bba*|b*
C、(a*b*)bb(a|b)*
D、(a*|b*)*bb(a*|b*)
答案
A
解析
在状态转换图中,每一个结点代表一个状态,其中双圈是终结状态。该题实际上是一个简化确定有限自动机(DFA)的过程,一个确定有限自动机可以通过消除多余状态和合并等价状态而转换成一个最小的与之等价的有限自动机。
首先介绍2个概念:最小状态DFA和等价状态。
最小状态DFA必须满足以下2个条件。
(1)没有多余状态(死状态):多余状态从该自动机的开始状态出发,任何输入串都不能到达的那个状态。
(2)没有2个状态是互相等价(不可区别)。
2个状态s和t如果同时满足下列2个条件,就称s和t是等价的。
(1)一致性:同是终态或同是非终态。
(2)蔓延性:从s出发读人某个a和从t出发读入某个a到达的状态等价。
本题的简化过程如下:
首先,将图中状态分为终态和非终态2个子集即({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}),因此,(2)空的正确答案为B。
重复子集划分步骤,发现新的状态无法再次划分。
所以,本题中2,3状态可以消除3状态,得到新的状态转换图如图3-2所示。
由图3-2可知终态2可以转换为正规表达式(a|b)*,同时必须输入连续2个b字符,才能完成0状态到终态2的转换,所以结果正规表达式必为形如“...bb(a|b)*”的字符串。又因为0和1之间由b和a轮回输入,可以表示为(ba)*,同时,状态0上输入a又回到自身,可以表示为a*。因此,(1)空的正确答案应该为(a*b*)*bb(a|b)*,根据正规式之间的代数性质,(a*b*)*bb(a|b)*与(a|b)*bb(a*b*)*等价。
转载请注明原文地址:https://kaotiyun.com/show/voxZ777K
本试题收录于:
软件设计师上午基础知识考试题库软考中级分类
0
软件设计师上午基础知识考试
软考中级
相关试题推荐
给出域名解析的两种方案。使用DNS服务器时,该服务器是哪个域名的主服务器?该域对应的IP地址是多少?
图中(a)、(b)、(c)、(d)为不同类型IPSee数据包的示意图,其中(1)和(2)工作在隧道模式;(3)和(4)支持报文加密。完成以下ACL配置,实现总部主机10.0.1.3和分支机构主机l0.0.2.3的通信。R1(eonfig)#acce
阅读以下说明,回答问题1~4,将解答填入对应的解答栏内。利用VLAN技术可以把物理上连接的网络从逻辑上划分为多个不同的虚拟子网,可以对各个子网实施不同的管理策略。图4-1是在网络中划分VLAN的连接示意图。使Switch1的千兆端口允许所有
阅读以下说明,回答问题1~3,将答案填入对应的解答栏内。网络地址转换(NAT)的主要目的是解决IP地址短缺问题以及实现TCP负载均衡等。在图4-1的设计方案中,与Internet连接的路由器采用网络地址转换。NAT按技术类型分为(10
在ServerA的IPSec安全策略配置过程中,ServerA和ServerB-之间通信的IPSec筛选器“许可”属性设置为“协商安全”,并且安全措施为“加密并保持完整性”,如图4-4所示。根据上述安全策略填写图4-5中的空格,表示完整的IPSec数据包格
访问控制表是防火墙实现安全管理的重要手段。完成下列访问控制列表(access-control-list)的配置内容,使内部所有主机不能访问外部IP地址段为202.117.12.0/24的Web服务器。Firewall(config)#access-
阅读以下说明,回答问题。(2010年下半年下午试题二)[说明]在Linux操作系统中,TCP/IP网络可通过若干文本文件及命令进行配置。文件/etc/sysconfig/network-scripts/eth0用于存储网络配置信息,请根据图5-6填写
Networkscanbeinterconnectedbydifferentdevices.Inthephysicallayer,networkscanbeconnectedby(66)orHubs,whichjust
图(a)中只有一个外部实体E1。使用【说明】中的词语,给出E1的名称。在进行系统分析与设计时,面向数据结构的设计方法(如Jackson方法)也被广泛应用。简要说明面向数据结构设计方法的基本思想及其适用场合。
随机试题
患者,男,25岁。突感上腹部剧痛。检查:血压130/80mmHg,脉搏110次/分,板样腹。肠鸣音消失。血红蛋白120g/L,血白细胞计数8.0×109/L。提示病情危险的是
某县公安局因张某拒绝交纳罚款,将张某汽车扣押一个月后,该局通知张某将汽车领回,但该车在扣押期间被使用,因发生交通事故而遭到部分损坏下列说法正确的是()
对于非施工单位原因造成的质量问题,应当由______返修,______承担责任。()
通过信函寻找代理商的优点是()。
简述课程实施中应注意的基本问题。
面对居高不下的房价,房租价格或许真的不算贵,但是为什么年轻人都觉得房租高呢?因为买房带来的远远不止居住的价值,但是租房,只能租来居住的价值。以下不能支持上述结论的是:
某公司办公室茶水间提供自助式收费饮料,职员拿完饮料后,自己把钱放到特设的收款箱中,研究者为了判断职员在无人监督时,其自律水平会受哪些因素的影响,特地在收款箱上方贴了一张装饰图片,每周一换。装饰图片有时是一些花朵,有时是一双眼睛。一个有趣的现象出现了:贴着“
设连续型随机变量X的分布函数为,试求:常数A和B;
Theteachersaidthattheearth______aroundthesun.
AnAustraliancompanyispreparedtogiveawaycolorTVsets,furcoats,diamondringsandachancetowin12000Australiandol
最新回复
(
0
)