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

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

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

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

软考中级

相关试题推荐
随机试题
最新回复(0)