什么不是nfa的成分?如何把NFA确定化为DFA的算法?

2023-03-22 11:46:20
来源:时代新闻网

现在大家都会在网络上汲取相关知识内容,比如nfa的要素_什么不是nfa的成分,为了更好的解答大家的问题,小编也是翻阅整理了相应内容,下面就一起来看一下吧!

什么不是nfa的成分?

初始状态集合不是NFA的成分。

如何把NFA确定化为DFA的算法?

把 NFA 确定化为 DFA 的算法实现

1)转换思路

由非确定的有限自动机出发构造与之等价的确定的有限自动机的办法是确定的有限自动机的状态对应于非确定的有限自动机的状态集合,即要使转换后的DFA的每一个状态对应NFA的一组状态。该DFA使用它的状态去记录在NFA读入一个输入符号后可能到达的所有状态,也就是说,在读入符号串a1a2a3…an之后,该DFA处在这样一个状态,该状态表示这个NFA的状态的一个子集T,而T是从NFA的开始状态沿着某个标记为a1a2a3…an的路径可以到达的那些状态。

2)消除空转移

消除N—>ε形式的产生式,即消除空转移。状态集合I的a弧转换Ia:定义为一状态集,是指从状态集I出发先经过a弧后再经过若干条ε弧而能到达的状态的集合。可以写作:Ia= ε-closure(J),J=move(I,a),其中,J是从I中任一状态出发经过一条a弧到达的状态集合记为move(I,a)。

s 表示NFA的状态,T 表示NFA的状态集合,a表示一个input symbol

ε-transition(ε转换)就是说input symbol为ε时的transition(转换)

3)数据流程图

以上就是全部内容,更多精彩请继续关注小编。

[责任编辑:]

为您推荐

相关推荐

内容举报联系邮箱:58 55 97 3 @qq.com

沪ICP备2022005074号-27 营业执照公示信息

Copyright © 2010-2020  看点时报 版权所有,未经许可不得转载使用,违者必究。