首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
如图3-1所示为一确定有限自动机(DFA)的状态转换图,与该自动机等价的正规表达式是(1),图中的(2)是可以合并的状态。
如图3-1所示为一确定有限自动机(DFA)的状态转换图,与该自动机等价的正规表达式是(1),图中的(2)是可以合并的状态。
admin
2005-03-15
103
问题
如图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
软件设计师上午基础知识考试
软考中级
相关试题推荐
A、B、C、D4台主机之间哪些可以直接通信?哪些需要通过设置网关(或路由器)才能通信?请画出网络连接示意图,并注明各个主机的子网地址和主机地址。不改变A主机的物理位置,将其IP地址改为192.155.12.168,试问它的直接广播地址和本地广播地址各是
A、B、C、D4台主机之间哪些可以直接通信?哪些需要通过设置网关(或路由器)才能通信?请画出网络连接示意图,并注明各个主机的子网地址和主机地址。若要加入第5台主机E,使它能与D主机直接通信,其IP地址的设定范围应是多少?
Linux在安装时会创建一些默认的目录,如下表所示:依据上述表格,在空(1)一(6)中填写恰当的内容(其中空1在候选答案中选择)。①对于多分区的Linux系统,文件目录树的数目是(1)。②Linux系统的根目录是(2),默认的用户主目录在(3)目录
根据该网络的需求,防火墙至少需要(14)个百兆接口和(15)个千兆接口。(15)
阅读以下说明,回答问题1至问题3,将解答填入对应的解答栏内。[说明]某单位网络的拓扑结构示意图如图5-1所示。该网络采用RIP协议,要求在R2上使用访问控制列表禁止网络192.168.20.0/24上的主机访问网络192.168.10.0/
阅读以下说明,回答问题。(2011年上半年下午试题四)[说明]某公司两分支机构之间的网络配置如图3-11所示。为保护通信安全,在路由器router-a和router-b上配置IPSec安全策略,对192.168.8.0/24网段和192.168.
阅读下列说明,回答问题,将解答填入对应栏内。【说明】图2—1是某企业网络拓扑,网络区域分为办公区域、服务器区域和数据区域,线上商城系统为公司提供产品在线销售服务。公司网络保障部负责员工办公电脑和线上商城的技术支持和保障工作。图2-1中,存储域网络
SDLC was invented by IBM to replace the older Bisynchronous protocol for wide area connections between IBM equipment. A varietio
MultipurposeInternetMailExtension(MIME)is a(46)document messaging standard in the Internet enviroment, with MIME, users can
The purpose of the requirements definition phase is to produce a clear, complete, consistent, and testable(6)of the technical re
随机试题
正当防卫
治疗阴虚发热,宜选用治疗肺热壅遏的咳喘,宜选用
根据《劳动合同法》,下列情形中,用人单位不得解除劳动者劳动合同的是()。
以下关于QDII基金的描述,不正确的是()。I.QDII基金的管理人可聘请境外投资顾问Ⅱ.QDII基金可单独或同时以人民币、美元等主要外币计算并披露净值信息Ⅲ.QDII基金一般直接由海外托管银行负责境内、境外资产的托管
生活中难免会遇到一些突发事件,我们要善于利用学过的知识,采取科学、有效的方法保护自己。如果发生了氯气泄漏,以下自救方法得当的是()。
①雪落在城外,也落在城内②温暖的房间里,有人用汤匙慢慢搅动一杯蜜汁③隔着结冰的河流,对岸是华灯灿烂的城市④杯勺碰撞的和声里,浓浓淡淡的花香冲逸开来,唤起多少鲜艳的回忆⑤蜜是花的情感,是融化的琥珀⑥这是白天从养蜂人那里买来的将以上6个句子重新排列
2011年1─8月,上海市接待“新马泰”游客()人次。
この建物の中ではどうぶつやことりを売っている。どうぶつ
Traditionalsuperstitionsandbeliefs【C1】______disappearaltogether;theyassumenewformsand【C2】______tocontemporarycond
Anewpartnerpushesouttwoclosefriendsonaverage,leavingloverswithasmallerinnercircleofpeopletheycanturntoin
最新回复
(
0
)