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

admin2009-02-15 64

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

本试题收录于：软件设计师上午基础知识考试题库软考中级分类

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

软考中级

相关试题推荐

随机试题

最新回复(0)

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

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

软考中级

光纤通信中使用的复用方式是(27)。E1载波把32个信道按(28)方式复用在一条2.048Mbit/s的高速信道上，每条话音信道的数据速率是(29)。

在WindowsNT中，采用两级页表的原因是(16)；当中断和异常发生并被系统捕捉后，系统将执行线程从用户态转换到(17)。

若某计算机系统是由500个元器件构成的串联系统，且每个元器件的失效率均为10-7/h，在不考虑其他因素对可靠性的影响时，该计算机系统的MTBF为(7)小时。

物理层的电气特性有多种标准，其中非平衡型标准规定(65)，电缆最大长度为(66)m。新的非平衡标准规定(67)，距离为10m时的最高数据率为(68)。在多种标准中，数据率最高的是新的平衡型标准，近距离传输其最高数据率可达(69)。

在无线通信中不能采用CSMA/CD方式，这是因为无线通信存在(59)，采用CSMA/CA技术是指(60)，MAC层的分布式协调功能提供(61)，站点发出的确认帧ACK，要在(62)间隔发送。为解决隐蔽站带来的问题，802.11允许(63)。

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

Ipv6is(71)for"InternetProtocolVersion6"。Ipv6isthe"nextgeneration"protocoldesignbytheIETFto(72)thecurrentversion

一个软件项目的活动图如图3—9所示，其中顶点表示项目里程碑，边表示包含的活动，边上的权重表示活动的持续时间，则里程碑()在关键路径上。

文法G＝({E),{+,,(,),a},P,E)，其中P由下列产生式组成E-＞E+E|EE|(E)|a。它生成由a,+,,(,)组成的算术表达式，该文法在乔姆斯基分层中属于(16)型文法，其对应的自动机是(17)，如产生句子aa+a，它的派生树是(

舞蹈作品：芭蕾舞剧《天鹅湖》

一慢性脓胸病人，闭式引流术后已半年，脓腔容积为10ml，病人一般情况尚好，下一步治疗最适宜的方法是（　　）。

为预防长期卧床患者发生肌肉萎缩，护士应着重指导家属学会()。

被称为“总预算”的是()。

预应力构件施二[属于先张法的工序是()。

“备案号”栏应填()。“商品名称，规格型号”栏应填()。

下列关于目标市场细分的说法，不正确的有()。

办理个人教育贷款时，签约与发放环节面临的操作风险不包括()。

“四书五经”是儒家经典的重中之重，下列属于“四书”的是()。

Forthispart,youareallowed30minutestowriteashortessay.Youshouldstartyouressaywithabriefdescriptionofthepi

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

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

软考中级

光纤通信中使用的复用方式是(27)。E1载波把32个信道按(28)方式复用在一条2.048Mbit/s的高速信道上，每条话音信道的数据速率是(29)。

在WindowsNT中，采用两级页表的原因是(16)；当中断和异常发生并被系统捕捉后，系统将执行线程从用户态转换到(17)。

若某计算机系统是由500个元器件构成的串联系统，且每个元器件的失效率均为10-7/h，在不考虑其他因素对可靠性的影响时，该计算机系统的MTBF为(7)小时。

物理层的电气特性有多种标准，其中非平衡型标准规定(65)，电缆最大长度为(66)m。新的非平衡标准规定(67)，距离为10m时的最高数据率为(68)。在多种标准中，数据率最高的是新的平衡型标准，近距离传输其最高数据率可达(69)。

在无线通信中不能采用CSMA/CD方式，这是因为无线通信存在(59)，采用CSMA/CA技术是指(60)，MAC层的分布式协调功能提供(61)，站点发出的确认帧ACK，要在(62)间隔发送。为解决隐蔽站带来的问题，802.11允许(63)。

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

Ipv6is(71)for"InternetProtocolVersion6"。Ipv6isthe"nextgeneration"protocoldesignbytheIETFto(72)thecurrentversion

一个软件项目的活动图如图3—9所示，其中顶点表示项目里程碑，边表示包含的活动，边上的权重表示活动的持续时间，则里程碑()在关键路径上。

文法G＝({E),{+,*,(,),a},P,E)，其中P由下列产生式组成E-＞E+E|E*E|(E)|a。它生成由a,+,*,(,)组成的算术表达式，该文法在乔姆斯基分层中属于(16)型文法，其对应的自动机是(17)，如产生句子a*a+a，它的派生树是(

舞蹈作品：芭蕾舞剧《天鹅湖》

一慢性脓胸病人，闭式引流术后已半年，脓腔容积为10ml，病人一般情况尚好，下一步治疗最适宜的方法是（ ）。

为预防长期卧床患者发生肌肉萎缩，护士应着重指导家属学会()。

被称为“总预算”的是()。

预应力构件施二[属于先张法的工序是()。

“备案号”栏应填()。“商品名称，规格型号”栏应填()。

下列关于目标市场细分的说法，不正确的有()。

办理个人教育贷款时，签约与发放环节面临的操作风险不包括()。

“四书五经”是儒家经典的重中之重，下列属于“四书”的是()。

Forthispart,youareallowed30minutestowriteashortessay.Youshouldstartyouressaywithabriefdescriptionofthepi

文法G＝({E),{+,,(,),a},P,E)，其中P由下列产生式组成E-＞E+E|EE|(E)|a。它生成由a,+,,(,)组成的算术表达式，该文法在乔姆斯基分层中属于(16)型文法，其对应的自动机是(17)，如产生句子aa+a，它的派生树是(

一慢性脓胸病人，闭式引流术后已半年，脓腔容积为10ml，病人一般情况尚好，下一步治疗最适宜的方法是（　　）。