首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
对于下图的非确定的有限状态自动机,其等价的正规表达式是(27)。
对于下图的非确定的有限状态自动机,其等价的正规表达式是(27)。
admin
2009-02-15
17
问题
对于下图的非确定的有限状态自动机,其等价的正规表达式是(27)。
选项
A、10(1|010)*
B、1*0(1|01*0)
C、1*0(1|01*0)*
D、10(1|010)
答案
C
解析
对于∑上的NFA M,可以构造一个∑上的正规式R,使得L(R)=L(M)。
现在把状态转换图的概念拓广,令每条弧可用一个正规式作标记。为∑上的NFA M构造相应的正规式R,分为以下两步。
①在M的状态转换图中加两个结点,一个x结点,一个y结点。从x结点到NFA M的初始状态结点引一条弧并用ε标记,从NFA M的所有终态结点到y结点引一条弧并用ε标记。形成一个与M等价的M’,M’中初态结点只有一个x且终态结点只有一个y。
②按下面的方法逐步消去M’中除x和y的所有结点。在消除结点的过程中,用正规式来标记弧,最后结点x和y之间的弧上的标记就是所求的正规式。消除结点的规则如下图所示。
对于题目中的原图的非确定的有限状态自动机,构造其等价正规式的过程如下:
转载请注明原文地址:https://kaotiyun.com/show/TkxZ777K
本试题收录于:
软件设计师上午基础知识考试题库软考中级分类
0
软件设计师上午基础知识考试
软考中级
相关试题推荐
当布线结构需要调整时,可通过布线配线系统来重新配置,具体调整手段是通过(31)来实现的。
在无线通信中不能采用CSMA/CD方式,这是因为无线通信存在(59),采用CSMA/CA技术是指(60),MAC层的分布式协调功能提供(61),站点发出的确认帧ACK,要在(62)间隔发送。为解决隐蔽站带来的问题,802.11允许(63)。
SSL握手协议定义了对SSL有效载荷进行常规(13)。SSL记录协议把报文中数据分成块,一块的大小是(14)。
SNMPv1是一个不安全的协议,管理站(Manager)与代理(Agent)之间通过(36)进行身份认证,由于认证信息没有加密,所以是不安全的。1998年公布的SNMPv3定义了基于用户的安全模型USM,其中的认证模块结合(37)算法形成认证协议,产生一个
在局域网标准中,(28)与FDDI的MAC帧格式较为相似。(29)介质访问控制方法对最短帧长度有要求,(30)对传输线路最短长度有要求。长10km,16Mbit/s,100个站点的令牌环,每个站点引入1位延迟位,信号传播速度位200m/us,则该环上1位延
阅读以下说明,回答下面问题。【说明】ADSL是接入Internet的一种宽带技术。下图1.9为一台带网卡的PC机采用ADSL接入Internet的网络结构图。
发展容错技术可提高计算机系统的可靠性。利用元件冗余可保证在局部有故障的情况下系统正常工作。带有热备份的系统称为(61)系统。它是(62),因此只要有一个子系统能正常工作,整个系统仍能正常工作。当子系统只能处于正常工作和不工作两种状态时,可以采用如图
Ipv6is(71)for"InternetProtocolVersion6"。Ipv6isthe"nextgeneration"protocoldesignbytheIETFto(72)thecurrentversion
阅读下列函数说明、图和C代码,将应填入(n)处的字句写在答题纸对应栏内。【说明】在进行文法分析的时候,通常需要检测一个单词是否在我们的单词列表里。为了提高查找和定位的速度,通常都要画出与单词列表所对应的单词查找树。程序构造一棵二叉排序树,每个节点存储一
文法G=({E),{+,*,(,),a},P,E),其中P由下列产生式组成E->E+E|E*E|(E)|a。它生成由a,+,*,(,)组成的算术表达式,该文法在乔姆斯基分层中属于(16)型文法,其对应的自动机是(17),如产生句子a*a+a,它的派生树是(
随机试题
A.气机不畅B.气滞C.气逆D.气陷E.气结气的运动受阻,运动不利时,称为
A.不超过25℃B.不超过20℃C.避光并不超过25℃D.避光并不超过20℃E.2℃~10℃药品质量标准“贮藏”项下的规定
工程内容验收包括()。
审计人员审查发现被审计单位当年部分销售货物被退回,销售业务已作账务处理而销售退回业务未作账务处理,不考虑其他因素,被审计单位可能存在的问题有()。
在实际中应用最为广泛的调查方式方法是()。
能将高级语言源程序转换成目标程序的是()。
控制图的控制对象为()。
[A]hospital[B]restaurant[C]map[D]zoo[E]school[F]hotel[G]clothes
Municipalbansonsmokinginrestaurantsandbarsarehighlycontroversial,buthistoryshowstheycanalsobehighlyeffective.
PressAssociationisanationalnewsagencyof
最新回复
(
0
)