首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
如图3-1所示为一确定有限自动机(DFA)的状态转换图,与该自动机等价的正规表达式是(1),图中的(2)是可以合并的状态。
如图3-1所示为一确定有限自动机(DFA)的状态转换图,与该自动机等价的正规表达式是(1),图中的(2)是可以合并的状态。
admin
2005-03-15
128
问题
如图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和问题2,将解答填入对应的解答栏内。二层隧道协议L2TP(Layer2TunnelingProtocol)是一种基于点对点协议PPP的二层隧道协议。某网络结构如图2所示,采用12TP来实现网络安全。
限制MailUser邮件主机里每个用户的邮箱大小不超过10MB,如何配置?如何设定邮件自动转发?如果向多个邮件地址进行邮件自动转发,如何配置?
限制MailUser邮件主机里每个用户的邮箱大小不超过10MB,如何配置?如何暂时禁用某个用户账号?
A、B、C、D4台主机之间哪些可以直接通信?哪些需要通过设置网关(或路由器)才能通信?请画出网络连接示意图,并注明各个主机的子网地址和主机地址。若要加入第5台主机E,使它能与D主机直接通信,其IP地址的设定范围应是多少?
请阅读以下说明和Socfort程序,将应填(n)处的字句写在对应栏内。网络应用的基本模型是客户机/服务器模型,这是一个不对称的编程模型,通信的双方扮演不同的角色:客户机和服务器。以下是一个简单的客户机程序(服务器程序略),其工作过程非常简单:客
MultipurposeInternetMailExtension(MIME)isa(71)documentmessagingstandardintheInternetenviroment,withMIME,userscans
Networkscanbeinterconnectedbydifferentdevices.Inthephysicallayer,networkscanbeconnectedby(66)orHubs,whichjust
Networkscanbeinterconnectedbydifferentdevices.Inthephysicallayer,networkscanbeconnectedby(66)orHubs,whichjust
SDLC was invented by IBM to replace the older Bisynchronous protocol for wide area connections between IBM equipment. A varietio
阅读以下说明、图和C代码。【说明】一般的树结构常采用孩子-兄弟表示法表示,即用二叉链表作树的存储结构,链表中结点的两个链域分别指向该结点的第一个孩子结点和下一个兄弟结点。例如,图10-8(a)所示的树的孩子-兄弟表示如图10-8(b)所示。
随机试题
钢筋}昆凝土板桩围堰适用于()河床。
前牙反颌矫治后是否复发,主要与
本病例当辨何证本病例的代表方为
肝在志为
1990年盖洛普民意调查表明:美国人民心目中最诚实和最道德的职业排序,在第一位的是
皮亚杰认为人的认知阶段发展可以分为感知运动、前运算、具体运算、_________运算等阶段。
88×87-89×86=?
现象与本质的对立主要表现在()。
在西方资本主义国家中,影响最大的两部法典是《法国民法典》和()。
非空的循环单链表head的尾结点P满足(45)。
最新回复
(
0
)