从文件读入一个非确定有穷状态自动机（NFA），用子集法将其确定化，并输出一个确定化的有穷状态自动机（DFA）。
原理：
流程图如下：
具体代码实现：
这里为了实现图形可视化，使用了graphviz，下载完成Graphviz工具后，需将其添加至系统环境变量中，且需将其上移至Matlab在系统环境变量中的路径之上。这样在Python中导入Graphviz工具包后，画图工具才能起作用，具体配置方法请自行百度…文章来源：https://www.toymoban.com/news/detail-726430.html
from graphviz import Digraph
# 空用“*”表示，规定第一个节点的空闭包为初态集合
# nodes:其中每个元素称为一个状态
# path：其中每个元素称为一个输入符号
# edges：是单值转换函数，表示一个状态node1，在输入字符path后，转到另一个状态node2
# start：初态集
# end：终态集
def Read_NFA_Data():
# 读入NFA数据
# 第一行为nodes（用“，”隔开），第二行为path（用“，”隔开）
# 第三行为edges（每个元素用“；”隔开，每个元素的数据用“，”隔开）
# 第四行为start（用“，”隔开），第五行为终态集（用“，”隔开）
with open('NFA.txt', 'r') as r:
lines = [line.rstrip('\n') for line in r.readlines()]
nodes = lines[0].split(',')
path = lines[1].split(',')
edges = lines[2].split(';')
edges = [x.split(',') for x in edges]
start = lines[3].split(',')
end = lines[4].split(',')
return nodes, path, edges, start, end
def NFA_Show(nodes, edges, start, end):
# 生成NFA图
NFA = Digraph('NFA', format='png')
for node in nodes:
if node in start:
NFA.node(node, shape='circle', color='red')
elif node in end:
NFA.node(node, shape='doublecircle')
else:
NFA.node(node, shape='circle')
for edge in edges:
NFA.edge(edge[0], edge[1], label=edge[2])
NFA.attr(rankdir='LR')
NFA.view()
def DFA_Show(D_nodes, D_edges, start, end):
# 生成DFA图
DFA = Digraph('DFA', format='png')
for n in D_nodes:
list_node = n.split(',')
if len(list(set(list_node) & set(end))) != 0 and list_node == start:
DFA.node(n, shape='doublecircle', color='red') # 该状态既是初态又是终结态
elif len(list(set(list_node) & set(end))) != 0:
DFA.node(n, shape='doublecircle') # 该状态是终结态
elif list_node == start:
DFA.node(n, shape='circle', color='red') # 该状态是初态
else:
DFA.node(n, shape='circle') # 该状态既不是初态也不是终结态
for e in D_edges:
DFA.edge(e[0], e[1], label=e[2])
DFA.attr(rankdir='LR')
DFA.view()
def move(my_nodes, my_path, my_edges):
# 定义单值转换函数
My_Node = []
for node in my_nodes:
for edge in my_edges:
if edge[0] == node and edge[2] == my_path:
My_Node.append(edge[1])
return My_Node
def closure(my_nodes, my_edges, My_Node=None):
# 定义求闭包的函数
if My_Node is None:
My_Node = my_nodes[::]
Temp = move(my_nodes, '*', my_edges)
todo = [x for x in Temp if x not in My_Node]
My_Node.extend(todo)
for each in todo:
closure(each, my_edges, My_Node)
My_Node = list(set(My_Node))
return My_Node
def is_in(Nodes, Temp):
# 判断Temp是否在Nodes中
for Node in Nodes:
if set(Node) == set(Temp):
return True
return False
def From_NFA_to_DFA(path, edges, start):
# 初始化DFA的状态和路径转换
D_nodes = []
D_edges = []
# 用子集法将NFA确定化为DFA
Start_node = start[::]
Start_Node = closure(Start_node, edges)
Nodes = [Start_Node]
location = 0
length = len(Nodes)
while location < length:
for p in path:
Temp_one = move(Nodes[location], p, edges)
Temp_two = closure(Temp_one, edges)
if Temp_two:
Last = ','.join(Nodes[location])
Next = ','.join(Temp_two)
D_edge = (Last, Next, p)
D_edges.append(D_edge)
D_nodes.append(Last)
if Temp_two != [] and is_in(Nodes, Temp_two) is False:
Nodes.append(Temp_two)
length = len(Nodes)
location += 1
return D_nodes, D_edges, Start_Node
if __name__ == '__main__':
N_nodes, N_path, N_edges, N_start, N_end = Read_NFA_Data() # 读入NFA数据
NFA_Show(N_nodes, N_edges, N_start, N_end) # 绘制NFA
D_Nodes, D_Edges, Start = From_NFA_to_DFA(N_path, N_edges, N_start) # NFA转换为DFA
DFA_Show(D_Nodes, D_Edges, Start, N_end) # 绘制DFA
读入文件内容：
X,0,1,2,3,Y
0,1
X,0,;0,0,0;0,1,;1,1,0;1,2,1;2,1,0;1,3,;3,3,0;3,Y,
X
Y
代码运行结果：
NFA:
DFA:
文章来源地址https://www.toymoban.com/news/detail-726430.html
到了这里，关于不确定有穷自动机NFA的确定化的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
