将Epsilon-NFA转换为NFA--python实现

1.任务要求

从具有epsilon的不确定有限状态自动机（NFA）得到一个无Epsilon 的NFA。

2.思路

Epsilon-NFA到NFA的目标主要是产生一个没有Epsilon边的，跟原状态图等价的新状态图。过程不复杂，首先从起始状态开始，寻找所有Epsilons边到达的对象的集合，然后复制这个集合的所有状态包含的非Epsilon状态。其实状态做完之后，寻找所有能够产生非Epsilon边的状态然后重复这个过程，最后NFA就出来了。

其本质就是使用无Epsilon的状态转换函数中的条件去替换有Epsilon的状态转换函数中的Epsilon，不断循环，最终实现NFA中的条件无Epsilon。

global nfa
nfa = parser.parse_fa()
closures = parser.parse_closures()
# TODO: implement thisprint(",".join(nfa['states']))
print(",".join(nfa['alphabet']))
print(nfa['start'])
print(",".join(nfa['final']))global dfa
dfa = {}
dfa['delta'] = []
dfa['final'] = nfa['final']start = nfa['start']
start_e = closures[start]begin = nfa['start']
alpha = nfa['alphabet']
delta = nfa['delta']
final = nfa['final']# seach all relations can arrive from a ,and m  is means the intermediate variable
# it means if a->b and b->c, then we van get a->c
def search(a, m, delta, closures):for re in closures[a]:for relation in delta:s, c, t = relationif re == s:if ((a, c, t)) not in h:h.append((a, c, t))
global h
# get others delta by adding a search function
for relation in delta:s, c, t = relationif c:dfa['delta'].append((s, c, t))h = dfa['delta']for a in nfa['states']:search(a, a, dfa['delta'], closures)for a in nfa['states']:for re in h:s, c, t = reif s == a:print("{},{},{}".format(s, c, t))print("end")

4.结果

输入：

输出：