首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
对于下图的非确定的有限状态自动机,其等价的正规表达式是(27)。
对于下图的非确定的有限状态自动机,其等价的正规表达式是(27)。
admin
2009-02-15
56
问题
对于下图的非确定的有限状态自动机,其等价的正规表达式是(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
软件设计师上午基础知识考试
软考中级
相关试题推荐
RS-232C是(36)之间的接口标准,它是(37)协议,其机械特性规定RS-232C的D型连接器有(38)个插脚。
RSA是一种基于(31)原理的公钥加密算法。网络上广泛使用的PGP协议采用RSA和IDEA两种加密算法组成链式加密体系,这种方案的优点是(32)。POP还可以对电子邮件进行认证,认证机制是用MD5算法产生(33)位的报文摘要,发送方用自己的RSA私钥对
为避免路由信息被重复发送,需要对路由信息包进行编号。如果网络中每台路由器每秒钟传送一次路由信息,为确保路由信息包的编号在1个月内不重复使用,则编号的最短长度应为(31)位。
在CMM软件过程的成熟度模型的(8)级别上,管理和工程的软件过程已经文档化、标准化,并综合成整个软件开发组织的标准软件过程。
请阅读以下说明和Socket程序,填入(n)处。【说明】以下是客户机/服务器模型中的一个简单的客户机程序(服务器程序略),其工作过程非常简单:客户机与服务器建立连接后,接收服务器向客户机返回的一条消息。程序中用到了两种结构hoste
发展容错技术可提高计算机系统的可靠性。利用元件冗余可保证在局部有故障的情况下系统正常工作。带有热备份的系统称为(61)系统。它是(62),因此只要有一个子系统能正常工作,整个系统仍能正常工作。当子系统只能处于正常工作和不工作两种状态时,可以采用如图
在软件开发过程中常用图作为描述工具。如DFD就是面向(6)分析方法的描述工具。在一套分层DFD中,如果某一张图中有N个加工(Process),则这张图允许有(7)张子图。在一张DFD图中,任意两个加工之间(8)。在画分层DFD时,应注意保持(9)之间的平
一台PC计算机系统启动时,首先执行的是(36),然后加载(37)。在设备管理中,虚拟设备的引入和实现是为了充分利用设备,提高系统效率,采用(38)来模拟低速设备(输入机或打印机)的工作。已知A、B的值和表达式A2/(5A+B)的求值过程,且A、B已
阅读下列函数说明、图和C代码,回答问题[说明]在进行文法分析的时候,通常需要检测一个单词是否在我们的单词列表里。为了提高查找和定位的速度,通常都要画出与单词列表所对应的单词查找树。程序构造一棵二叉排序树,每个节点存储一个单词,按字典序列,
对文法G进行改写,然后对每个非终结符写出不带回溯的递归子程序。经改写后的文法是否是LL(1)的?指出它的预测分析表中(1)~(3)处的内容。
随机试题
患者,男,36岁。平素嗜酒,今晨脘腹痞闷,口苦纳少,口干不欲饮,舌红苔黄腻,脉滑数。治疗最佳方为
女性,35岁。诉水肿就诊。尿液检查蛋白(+),红细胞5~10个/HP,白细胞2~3个/HP,颗粒管型0~2个/HP,拟诊慢性肾炎。体检时最可能发现水肿的部位是
关于刑事诉讼法定代理人与诉讼代理人的区别,下列哪些选项是正确的?
()是中华民族的优良传统,是一个人立足于社会的基本准则,也是对从业者的道德要求。
在借贷记账法下,将账户划分为借、贷两方,哪一方登记增加,哪一方登记减少的依据是()。
下列各项中,不属于社会审计实施阶段工作的是()。
张先生提前为3岁的儿子未来的小学教育进行投资规划,下列投资中比较适合的是()。
单利和复利的区别在于()。
LRU页面调度算法是选择()的页面先调出。
A、JasondamagedMike’scarinanoccident.B、Jasonjustboughtanewcar.C、JasonboughtanewcarforMike.D、Jasoncouldn’tfi
最新回复
(
0
)