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

admin2009-02-15 58

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

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

软考中级

若海明码的监督关系为：S0=a0+a3+a4+a6；S1=a1+a3+a5+a6：S2=a2+a4+a5+a6。若需发送的信息为：1101，则信道中传输的码字为(12)，该海明码的编码效率为(13)。

在图4-1所示的系统中，R1、R2、R3为3个加工部件，每个加工部件的失效率均为λ，可靠性均为尺。则该系统的可靠性为(4)。若每个加工部件的平均无故障时间为5000小时，则该系统的平均无故障时间为(5)小时。

以下Windows命令中，可以用于验证端系统地址的是(56)；可以用于识别分组传送路径的是(57)；如果要终止一个ping会话，正确的操作是(58)。以下应用中，对网络带宽性能影响最大的应用是(59)。OSPF和RIP都是Internet中的路由协议，与R

简单网络管理协议SNMPv2定义用于计算收到的分组数或字节数的Counter64数据类型，其特性是(41)。

既能用于新的陆上网络，又可对现有系统进行升级改造，特别适用于DWDM系统传输的是()光纤。

以下对施工企业项目经理的工作性质的说明，正确的是(　　)。

下列属于影响可转换公司债券价值的因素为()。

关于库存商品、发出商品的核算,下列说法正确的有()。

根据《企业所得税法》的规定，企业的下列各项支出，在计算应纳税所得额时，准予从收入总额中直接扣除的有()。

镜泊湖是大约1万年前，由于()而形成的。

教育电视台是指教育行政部门开办的专业电视台。（）

TheAmericanFamilyIntheAmericanfamilythehusbandandwifeusuallyshareimportantdecisionmaking.Whenthechildrenare(5

Therearethreekindsofgoals:short-term,medium-rangeandlong-termgoals.Short-rangegoalsarethosethatusuallydealwith

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

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

软考中级

若海明码的监督关系为：S0=a0+a3+a4+a6；S1=a1+a3+a5+a6：S2=a2+a4+a5+a6。若需发送的信息为：1101，则信道中传输的码字为(12)，该海明码的编码效率为(13)。

在图4-1所示的系统中，R1、R2、R3为3个加工部件，每个加工部件的失效率均为λ，可靠性均为尺。则该系统的可靠性为(4)。若每个加工部件的平均无故障时间为5000小时，则该系统的平均无故障时间为(5)小时。

以下Windows命令中，可以用于验证端系统地址的是(56)；可以用于识别分组传送路径的是(57)；如果要终止一个ping会话，正确的操作是(58)。以下应用中，对网络带宽性能影响最大的应用是(59)。OSPF和RIP都是Internet中的路由协议，与R

简单网络管理协议SNMPv2定义用于计算收到的分组数或字节数的Counter64数据类型，其特性是(41)。

既能用于新的陆上网络，又可对现有系统进行升级改造，特别适用于DWDM系统传输的是()光纤。

以下对施工企业项目经理的工作性质的说明，正确的是( )。

下列属于影响可转换公司债券价值的因素为()。

关于库存商品、发出商品的核算,下列说法正确的有()。

根据《企业所得税法》的规定，企业的下列各项支出，在计算应纳税所得额时，准予从收入总额中直接扣除的有()。

镜泊湖是大约1万年前，由于()而形成的。

教育电视台是指教育行政部门开办的专业电视台。（）

TheAmericanFamilyIntheAmericanfamilythehusbandandwifeusuallyshareimportantdecisionmaking.Whenthechildrenare(5

Therearethreekindsofgoals:short-term,medium-rangeandlong-termgoals.Short-rangegoalsarethosethatusuallydealwith

以下对施工企业项目经理的工作性质的说明，正确的是(　　)。