编译原理构造r*(闭包运算)的NFA 算法流程图
2016-09-11 17:28:38 0 举报
构造r*(闭包运算)的NFA算法流程图主要包括以下步骤: 1. 初始化一个空的NFA集合。 2. 对于给定的DFA,遍历其所有状态和转换。 3. 对于每个状态,创建一个新的状态并将其添加到NFA集合中。 4. 对于每个转换,创建一个新的转换并将其添加到NFA集合中。 5. 对于每个新的转换,将其源状态和目标状态分别设置为DFA中的源状态和目标状态。 6. 对于每个新的转换,将其接受条件设置为DFA中的接受条件。 7. 重复步骤2-6,直到所有的DFA状态和转换都被处理完毕。 8. 返回构造好的NFA集合。
作者其他创作
大纲/内容
ε_Closure(I)的构造,即经任意条ε弧而能到达的任何状态都属于ε_Closure(I)
NFA确定化为DFA
令所有的终结结点用空边指向所有的起始结点
然后对上表中第一列的个各状态子集重命名得到一个新的状态转换矩阵,该状态装换矩阵对应一个与NFA M等价的DFA M’。
将S用空边指向所有的起始节点。所有之前的终结结点用空边指向Y。S用空边指向Y结点。
从文件中读取给定的正规式r,其NFA为M
构造正规式r*(闭包运算)的NFA M'
0 条评论
下一页