首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
如图3-1所示为一确定有限自动机(DFA)的状态转换图,与该自动机等价的正规表达式是(1),图中的(2)是可以合并的状态。
如图3-1所示为一确定有限自动机(DFA)的状态转换图,与该自动机等价的正规表达式是(1),图中的(2)是可以合并的状态。
admin
2005-03-15
64
问题
如图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
软件设计师上午基础知识考试
软考中级
相关试题推荐
阅读以下说明,回答问题1~4,将解答填入对应栏内。A公司用一台Web服务器和一台应用服务器来管理销售信息。销售人员在办公室时通过PC机来访问应用服务器,若在公司以外,则通过移动电话或PDA(PersonalDigitalAssistant)访问公司网
通常VLAN有哪两种实现方式。在基于端口的VLAN划分中,交换机上的每一个端口允许以哪3种模式划入VLAN中,并简述它们的含义。
阅读以下说明,回答问题1~3,将解答填入对应的解答栏内。网络解决方案如图2所示,该网络原先使用的使国外品牌的交换机,随着网络规模的扩大,增添了部分国产的交换机,交换机1~5均是国产10M/100Mbit/s自适应交换机,交换机6和交换机7是第3层交换机
限制MailUser邮件主机里每个用户的邮箱大小不超过10MB,如何配置?限制MailUser邮件主机里所有用户接收的单个邮件的大小不超过5MB,如何配置?
在WindowsServer2003的“路由和远程访问”中提供两种隧道协议来实现VPN服务:(1)和L2TP,L2TP协议将数据封装在(2)协议帧中进行传输。 为了加强远程访问管理,新建一条名为“SubInc”的访问控制策略,允许来自子公司服务器
阅读以下说明,回答问题。(2011年上半年下午试题二)[说明]Linux系统有其独特的文件系统ext2,文件系统包括文件的组织结构、处理文件的数据结构及操作文件的方法。可以通过命令获取系统及磁盘分区状态信息,并能对其进行管理。在Linux中,
网络存储备份系统的设计目标是什么?
阅读以下说明,回答问题。(2010年上半年下午试题二)[说明]在Linux服务器中,inetd/xinetd是Linux系统中的一个重要服务。xinetd可使用Only_frorn、no_access以及access_tirues等参数对用户
阅读以下说明,回答问题,将解答填入答题纸对应的解答栏内。【说明】图2-1为某公司数据中心拓扑图,两台存储设备用于存储关系型数据库的结构化数据和文档、音视频等非结构化文档,规划采用的RAID组合方式如图2-2、图2-3所示。图2-2所示的RAID方
Traditional Internet access methods like dial-up were so slow that host computers were connected to the dial-up(71)at the custom
随机试题
弥散性血管内凝血(DIC)发生广泛出血的主要原因是
11个月男婴,弛张高热,咳嗽6天,精萎纳差,时有呕吐,周围血象白细胞26乘以十的九次方/L,查体:烦躁不安,气促,面色苍白,皮肤可见猩红热样皮疹,两肺可闻中小湿啰音。
固定资产按项目建设阶段分类,可以分为()。
某建筑工程,建筑面积23824m2,地上10层,地下2层(地下水位-2.0m)。主体结构为非预应力现浇混凝土框架一剪力墙结构(柱网为9m×9m,局部柱距为6m),梁模板起拱高度分别为20、12mm。抗震设防烈度7度。梁、柱受力钢筋为HRB335,接头采用挤
某工程双代号网络计划如图l所示(时间单位:天),其关键线路为()条。
依据《证券投资基金法》的规定,不得担任基金管理人的董事、监事、高级管理人员和其他从业人员的情形不包括()。
五指峰、玉京峰、汉阳峰、大塔山依次是()的主峰。
下列做法中,符合所属企业职业道德要求的是()。
用社会存在和社会意识辩证关系的原理,说明大力发展社会主义先进文化的意义。
Severaldaysago,Icameacrossastrangerinthestreetwhostoppedandaskedmedirections.I【C1】________toshowhimtheway
最新回复
(
0
)