对于下图的非确定的有限状态自动机，其等价的正规表达式是(27)。

admin2009-02-15 83

问题对于下图的非确定的有限状态自动机，其等价的正规表达式是(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)

对于下图的非确定的有限状态自动机，其等价的正规表达式是(27)。

软件设计师上午基础知识考试

软考中级

为了进行差错控制，必须对传送的数据帧进行校验。如果CRC的生成多项式为G(X)=X4+X+1，信息码字为10110，则在信道中传输的码字是(16)。

我国政府部门的电子政务应用系统通常基于(15)，通过政府门户网站为社会公众提供服务。

HTTP协议是常用的应用层协议，它通过(22)协议提供服务，上下层协议默认时，使用(23)端口进行服务识别。HTTP双方的一次会话与上次会话是(24)，即协议是无状态的。从交换信息的整体性说是(25)，SHTTP对HTTP的扩展在于(26)。

在面向对象分析过程中，用概念模型来详细描述系统的问题域，用(5)来表示概念模型。(6)关系用于表示类与类、接口与接口之间的继承关系；在Java中，用(7)关键字来直接表示这种关系。

某电子商务公司由相对独立的6个子公司组成，在管理上其中3个子公司管理基础完善，基本达到科学管理的要求。企业高层为企业长远发展考虑决定建设一个基于B/S结构的管理信息系统。该系统项目可使用(6)进行开发建设。

Foreachblank,choosethebestanswerfromthefourchoicesandwritedownontheanswersheet.(66)isaone-wayfunctiont

A、主动脉瓣关闭不全B、高血压、甲状腺功能亢进症C、两者均有D、两者均无颈静脉搏动出现于()

男性，30岁，由高处跌落，引起骨盆骨折及股骨开放性骨折，伤口大量出血，现场急救治疗首先应进行

麻子仁丸使用于（　　）。

K银行对在建工程项目享有()。

曳引式电梯设备进场验收合格后，在驱动主机安装的工序是()。

一张面额6000元的商业汇票4个月后到期，年现率为1096，贴现利息应为()。

根据企业所得税法律制度的规定，企业发生的下列支出中，在计算应纳税所得额时准予扣除的是()。

教师讲解“所以动心忍性，曾益其所不能”中“所以”的词义，另举一例加以说明，下列合适的是()。

促使第三世界在国际舞台的崛起，并成为决定国际事务的重要力量的标志是()。

对于下图的非确定的有限状态自动机，其等价的正规表达式是(27)。

软件设计师上午基础知识考试

软考中级

为了进行差错控制，必须对传送的数据帧进行校验。如果CRC的生成多项式为G(X)=X4+X+1，信息码字为10110，则在信道中传输的码字是(16)。

我国政府部门的电子政务应用系统通常基于(15)，通过政府门户网站为社会公众提供服务。

HTTP协议是常用的应用层协议，它通过(22)协议提供服务，上下层协议默认时，使用(23)端口进行服务识别。HTTP双方的一次会话与上次会话是(24)，即协议是无状态的。从交换信息的整体性说是(25)，SHTTP对HTTP的扩展在于(26)。

在面向对象分析过程中，用概念模型来详细描述系统的问题域，用(5)来表示概念模型。(6)关系用于表示类与类、接口与接口之间的继承关系；在Java中，用(7)关键字来直接表示这种关系。

某电子商务公司由相对独立的6个子公司组成，在管理上其中3个子公司管理基础完善，基本达到科学管理的要求。企业高层为企业长远发展考虑决定建设一个基于B/S结构的管理信息系统。该系统项目可使用(6)进行开发建设。

Foreachblank,choosethebestanswerfromthefourchoicesandwritedownontheanswersheet.(66)isaone-wayfunctiont

A、主动脉瓣关闭不全B、高血压、甲状腺功能亢进症C、两者均有D、两者均无颈静脉搏动出现于()

男性，30岁，由高处跌落，引起骨盆骨折及股骨开放性骨折，伤口大量出血，现场急救治疗首先应进行

麻子仁丸使用于（ ）。

K银行对在建工程项目享有()。

曳引式电梯设备进场验收合格后，在驱动主机安装的工序是()。

一张面额6000元的商业汇票4个月后到期，年现率为1096，贴现利息应为()。

根据企业所得税法律制度的规定，企业发生的下列支出中，在计算应纳税所得额时准予扣除的是()。

教师讲解“所以动心忍性，曾益其所不能”中“所以”的词义，另举一例加以说明，下列合适的是()。

促使第三世界在国际舞台的崛起，并成为决定国际事务的重要力量的标志是()。

麻子仁丸使用于（　　）。