[编译原理实验]python实现NFA的确定化 |
您所在的位置：网站首页 › 正规式转换成dfa › [编译原理实验]python实现NFA的确定化 |
[编译原理实验]python实现NFA的确定化
|
[编译原理实验2]python导入Graphviz实现NFA的确定化
实验要求输入文件数据结构关键代码1.文件读入处理2.画NFA图像3.找到所有NFA状态的空闭包集合4.求NFA状态的等价状态5.DFA的状态遇到输入字符的状态转换情况6.画DFA图像
完整python代码测试样例2文件读入输出
小结
实验要求
从txt文件读入NFA；用Graphviz实现自动机的图形化；输出NFA和DFA图像；
输入文件
data.txt 第一行为初态集合,第二行为终态集合 其余是状态转换情况(ps. 本实验$代表空ε) 0 10 0 $ 1 1 $ 2 1 $ 4 2 a 3 3 $ 6 4 b 5 5 $ 6 6 $ 7 7 a 8 8 b 9 9 b 10 6 $ 1 0 $ 7 数据结构 Move_NFA ,list类型的list,存放NFA状态变化情况._closure ,字典,存放NFA中每个状态的空闭包集合Res,字典,存放当前状态遇到每个输入字符的后续状态集,如{‘a’:[‘4’,‘1’,‘2’,‘3’,‘7’,‘6’, ‘8’]}State0 ,list类型,存放NFA的所有状态Str0,list类型,存放NFA的字母表StateList,list类型的列表,存放DFA的所有状态集合.Begin0,End0,list类型,Begin0为DFA的初态集合,End0为DFA的终态集 关键代码 1.文件读入处理 with open('data.txt', 'r') as r: NFA = [line.rstrip('\n') for line in r.readlines()] Move_NFA = NFA[2::] for i in range(len(Move_NFA)): # print(Move_NFA[i]) Move_NFA[i] = Move_NFA[i].split() # 以空格为分隔符分开 2.画NFA图像需要导入Graphviz库及下载Graphviz. from graphviz import Digraph def graph_nfaprint(): # 画NFA的图像 g = Digraph('G', filename='NFA.gv', format='png') for i in range(len(Move_NFA)): g.edge(Move_NFA[i][0], Move_NFA[i][2], label=Move_NFA[i][1]) for i in range(len(Begin)): g.node(Begin[i], color='red') # 开始节点红色 for j in range(len(End)): g.node(End[j], shape='doublecircle') # 结束节点双层 g.view()输出: 求出ε-closure(s)，ε-closure(s)表示由状态s经由条件ε可以到达的 所有状态的集合 for i in range(len(State0)): res = [State0[i]] for j in range(len(Move_NFA)): if Move_NFA[j][0] == State0[i] and Move_NFA[j][1] == '$': # 查找空闭包 res.extend(Move_NFA[j][2]) _closure[State0[i]]=list(set(res)) # print(_closure ) 4.求NFA状态的等价状态输入为单个状态,返回一个List def Findclosure(AA): # 输入一个状态,找这个状态的所有等价状态 A = _closure[AA] # 查询输入状态的空闭包 A0 = [] for ch in A: A0 = A0 + _closure[ch] A0 = list(set(A0)) while set(A) != set(A0): # 循环直到闭包集合不再变化,得到最终的结果 A = A0 A0 = [] for ch in A: A0 = A0 + _closure[ch] A0 = list(set(A0)) return A0 5.DFA的状态遇到输入字符的状态转换情况构造状态转换表,普遍称为称move函数 如本例: ε-closure(0) = A ε-closure(move(A,a)) = ε-closure({3,8}) = {1,2,3,4,6,7,8} = B ε-closure(move(A,b)) = ε-closure(5) = {1,2,4,5,6,7} = C ε-closure(move(B,a)) = ε-closure({3,8}) = {1,2,3,4,6,7,8} = B ε-closure(move(B,b)) = ε-closure({5,9}) = {1,2,4,5,6,7,9} = D ε-closure(move(C,a)) = ε-closure({3,8}) = {1,2,3,4,6,7,8} = B ε-closure(move(C,b))=ε-closure(5) = {1,2,4,5,6,7} = C ε-closure(move(D,a)) = ε-closure({3,8}) = {1,2,3,4,6,7,8} = B ε-closure(move(D,b)) = ε-closure(5) = {1,2,4,5,6,7} = C abABCBBDCBCDBC def FindNewState(AB): # 找DFA状态的单步集合 res = dict() # 字典,形如{'a': ['4', '1', '2', '3', '7', '6', '8'], 'b': ['5', '4', '1', '2', '7', '6']} for ch in Str0: RES = [] for i in range(len(AB)): for j in range(len(Move_NFA)): if Move_NFA[j][0] == AB[i] and Move_NFA[j][1] == ch: RES.append(Move_NFA[j][2]) result = [] for k in RES: result = result+Findclosure(k) res[ch] = list(set(result)) return res 6.画DFA图像DFA的初始状态是NFA的初始状态的等价状态,终止状态是含有NFA终止状态的所有集合 def graph_dfaprint(StateList, Begin0, End0): # 画DFA图像 g = Digraph('G', filename='DFA.gv', format='png') Begin1 = [] End1 = [] for i in range(len(Begin0)): Begin1.append(" ".join(sorted(Begin0[i]))) for j in range(len(End0)): End1.append(" ".join(sorted(End0[j]))) # 从小到大排序 for i in range(len(StateList)): Dictt = FindNewState(StateList[i]) for j in Str0: if StateList[i] != [] and Dictt[j] != []: # 防止重复 g.edge(" ".join(sorted(StateList[i])), " ".join(sorted(Dictt[j])), label=j) for k in range(len(Begin1)): g.node(Begin1[k],color='red', shape='circle') # 初态结点为红色 for i in range(len(StateList)): g.node(" ".join(sorted(StateList[i])), shape='circle') # 所有节点为圆形 for j in range(len(End1)): g.node(End1[j], shape='doublecircle') # 终态结点为双层 g.view()输出: |
【本文地址】
今日新闻 |
推荐新闻 |