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

admin2009-02-15 55

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

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

软考中级

计算机系统的性能评价有多种方法，在关于各种性能评价方法的描述中，说法有误的是(64)。

在下列关于网络运行机制和所提供的服务的描述中，在帧中继网络中不(68)。

当使用一个公用分组交换网络时，用户负责下列任务中的(23)。

某请求分页存储管理系统中，容量为1MB的主存被划分为512块，其页表如表7-1所示。若给定一十进制逻辑地址为7058，其十进制物理地址是(11)。

Foreachblank,choosethebestanswerfromthefourchoicesandwritedownontheanswersheet.(66)isaone-wayfunctiont

In　the　following　essay,　each　blank　has　four　choices.　Choose　the　most　suitable　one　from　the　four　choices　and　write　down　in　the　an

算术表达式a+(1)一c)d的后缀式是(10)(-、+、表示算术的减、加、乘运算，运算符的优先级和结合性遵循惯例)。

测定节支可能性或寻求节支领域的方法就是（）

对接触铅作业人员的营养，应注意补充较大剂量的维生素是

协助君、臣药加强治疗作用，或直接治疗次要的兼证的药物根据病情需要，用与君药性味相反而又能在治疗中起相成作用的药物

某咨询公司接受委托进行某项目的可行性研究，有关人员提出有两种工艺方案可供选择。采用这两种工艺的有关财务数据见表6-1。问题1．若基准收益率为12%，咨询工程师应如

凡是有价证券都是我国《票据法》上所指的票据。()

如果企业账面应保留的材料成本大于账面材料成本，则下列说法中正确的是()。

下列各项，影响固定资产折旧的因素有（）。

下列各项中，属于约束性固定成本的有()。

以下面谱例中的旋律作为主题，分别写作三段变奏。主题：要求：变奏一：进行加花变奏。

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

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

软考中级

计算机系统的性能评价有多种方法，在关于各种性能评价方法的描述中，说法有误的是(64)。

在下列关于网络运行机制和所提供的服务的描述中，在帧中继网络中不(68)。

当使用一个公用分组交换网络时，用户负责下列任务中的(23)。

某请求分页存储管理系统中，容量为1MB的主存被划分为512块，其页表如表7-1所示。若给定一十进制逻辑地址为7058，其十进制物理地址是(11)。

Foreachblank,choosethebestanswerfromthefourchoicesandwritedownontheanswersheet.(66)isaone-wayfunctiont

In the following essay, each blank has four choices. Choose the most suitable one from the four choices and write down in the an

算术表达式a+(1)一c)*d的后缀式是(10)(-、+、*表示算术的减、加、乘运算，运算符的优先级和结合性遵循惯例)。

测定节支可能性或寻求节支领域的方法就是（）

对接触铅作业人员的营养，应注意补充较大剂量的维生素是

协助君、臣药加强治疗作用，或直接治疗次要的兼证的药物根据病情需要，用与君药性味相反而又能在治疗中起相成作用的药物

某咨询公司接受委托进行某项目的可行性研究，有关人员提出有两种工艺方案可供选择。采用这两种工艺的有关财务数据见表6-1。问题1．若基准收益率为12%，咨询工程师应如

凡是有价证券都是我国《票据法》上所指的票据。()

如果企业账面应保留的材料成本大于账面材料成本，则下列说法中正确的是()。

下列各项，影响固定资产折旧的因素有（）。

下列各项中，属于约束性固定成本的有()。

以下面谱例中的旋律作为主题，分别写作三段变奏。主题：要求：变奏一：进行加花变奏。

In　the　following　essay,　each　blank　has　four　choices.　Choose　the　most　suitable　one　from　the　four　choices　and　write　down　in　the　an

算术表达式a+(1)一c)d的后缀式是(10)(-、+、表示算术的减、加、乘运算，运算符的优先级和结合性遵循惯例)。