首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
如图3-1所示为一确定有限自动机(DFA)的状态转换图,与该自动机等价的正规表达式是(1),图中的(2)是可以合并的状态。
如图3-1所示为一确定有限自动机(DFA)的状态转换图,与该自动机等价的正规表达式是(1),图中的(2)是可以合并的状态。
admin
2005-03-15
111
问题
如图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
软件设计师上午基础知识考试
软考中级
相关试题推荐
在OSI参考模型有哪几层?NetBIOS包括哪些服务功能?
请列举IEEE802.11b的两种工作模式。列举蓝牙产品采用的主要技术内容。
NAT按技术类型分为哪3种转换方式?请解释画线部分内容含义?
在ServerA的IPSec安全策略配置过程中,ServerA和ServerB-之间通信的IPSec筛选器“许可”属性设置为“协商安全”,并且安全措施为“加密并保持完整性”,如图4-4所示。根据上述安全策略填写图4-5中的空格,表示完整的IPSec数据包格
根据网络拓扑和需求说明,完成(或解释)路由器R1的配置。R1#configureterminal;进入全局配置模式R1(config)#interraceethernet0;进入端口配嗣模式R1(config-i
根据网络拓扑和需求说明,完成(或解释)路由器R1的配置。R1#configureterminal;进入全局配置模式R1(config)#interraceethernet0;进入端口配嗣模式R1(config-i
阅读以下说明,回答以下问题,将解答填入答题纸对应的解答栏内。【说明】某单位网络拓扑结构如下图所示,该单位.Rotlter以太网接口E0接内部交换机S1,S0接口连接到电信ISP的路由器;交换机S1连接内部的Web服务器、DHCP服务器、
阅读以下说明,回答问题。(2010年上半年下午试题二)[说明]在Linux服务器中,inetd/xinetd是Linux系统中的一个重要服务。xinetd可使用Only_frorn、no_access以及access_tirues等参数对用户
SOXisanalternativesyntaxfor(71).ItisusefulforreadingandcreatingXMLcontentinatexteditor.Itistheneasilytran
The purpose of the requirements definition phase is to produce a clear, complete, consistent, and testable(6)of the technical re
随机试题
声像图显示脾实质低回声团块,不包括
男,48岁。腹胀3个月。查体:腹壁静脉曲张,腹水征(+),脾大。该患者腹壁静脉血流方向应为
一台并励直流电动机,PN=7.2kW,UN=110V,nN=900r/min,ηN=85%,Ra=0.08Ω(含电刷接触压降),If=2A,当电动机在额定状态下运行,若负载转矩不变,在电枢回路中串入一电阻,使电动机转速下降到450r/min,那么此电阻的阻
证券公司对客户的授信和融出资金、证券均应由公司总部统一控制和办理,严禁分支机构擅自对外办理相关业务。()
金融企业应在每批次不良资产转让工作结束后()个工作日内,向同级财政部门和中银监会或属地银监局报告转让方案及处置结果。
感觉仅依赖个别感觉器官的活动,而知觉依赖多种感觉器官的联合活动。
关于职业道德修养的说法,正确的是()。
刘国平是上海某高新技术企业的总经理,现在他需要了解某些有关高新技术企业的政策,以便作出战略决策。于是,他指示总经理办公室的小马,尽快整理出一份有关高新技术企业的政策文件并交给他。请参照“示例1.jpg”和“示例2.jpg”,利用考生文件夹下提供的相关素材文
Traditionally,universitieshavecarriedouttwomainactivities:researchandteaching.Manyexpertswouldarguethatboththes
Desktoppublishingsystemisamodernpublishingsystemwhichmakesuseofcomputertechnology,graphicskillsandprintingtech
最新回复
(
0
)