前言
分析
首先分析题目，需要两个类：DFA类和NFA类
需要写四个核心函数：move函数、smove函数、closure函数和nfa_to_dfa函数
另外提前说一下下面代码中一些变量的表示方法：
（1）状态：NFA的状态都用数字表示，DFA的状态因为包含了多个NFA的状态，所以DFA的状态是一个包含了很多列表的列表，例如：
NFA：0, 1, 2, 3, …… // 0,1,2,3都代表NFA的某一状态
DFA：[0, 1]，[1, 2], …… // [0, 1]，[1, 2]都代表DFA的某一状态
（2）状态集：使用列表存放状态，例如
NFA：[0, 1, 2, 3, ……] // 0,1,2,3代表状态
DFA：[[0, 1], [1, 2], [2, 3], ……] // [0, 1]是DFA的第一个状态，[1， 2]是DFA的第二个状态
（3）状态转换集：使用列表嵌套列表，里面的列表再嵌套字典，不懂的可以滑倒下面看一下运行结果，运行结果里面表示的很清楚，这里简单说下，例如：
NFA：[[{'遇到的字符'： '下一状态'}, ……], [{'遇到的字符'： '下一状态'}, ……], [{'遇到的字符'： '下一状态'}, ……],……] // 比如NFA总共有五个状态，那么最外面的列表就包含了五个子列表——代表每个状态，然后在每个子列表里存放字典，key用遇到的字符，value表示下一状态。
DFA：同上
（4）初态和终态：都是数字
数据输入
我测试的时候，使用的NFA如下，如果需要计算其他的NFA，可以自己输入NFA的信息或者修改输入文件：
代码实现
由于测试的时候不想输入太多，所以在设计交互的时候，用户随便输入就行，系统会自动从文件读取需要输入的NFA信息，所以这里也附上NFA信息的txt文件，需要和下面的代码放在同一文件夹下，下面的代码运行时直接全部输入1，就能得到正确答案！
import copy
class NFA:
# 初始化函数，传入状态集、输入集、转移函数集、初态、终态
def __init__(self, states, my_inputs, move, s, e):
self.states = states
self.my_inputs = my_inputs
self.move = move
self.s = s
self.e = e
def to_string(self):
print("===================")
print("状态集如下：")
count = 0
for i in self.states:
count = count + 1
if count == len(self.states):
print(i)
else:
print(i, end=",")
print("===================")
print("输入集如下：")
count = 0
for i in self.my_inputs:
count = count + 1
if count == len(self.my_inputs):
print(i)
else:
print(i, end=",")
print("===================")
print("转移函数如下：")
print(self.move)
for i in self.states:
print(str(i) + "状态：", end="")
if len(self.move[i]) == 0:
print(str(i) + "状态无转换集")
else:
if len(self.move[i][0].keys()) == 0:
print(str(i) + "状态无转换集")
else:
for j in self.move[i]:
str_1 = list(j.keys())[0]
next_state = int(j[str_1])
print(str(i) + "->" + str(next_state), end=" ")
print("\n", end="")
print("====================")
print("初态为：" + str(self.s))
print("====================")
print("终态为：" + str(self.e))
def move_function(self, state, one_str):
result = []
if len(self.move[state]) == 0:
return None
else:
if len(self.move[state][0].keys()) == 0:
return None
else:
for j in self.move[state]:
if one_str == list(j.keys())[0]:
next_state = int(j[one_str])
result.append(next_state)
if len(result) == 0:
return None
else:
return result
def smove_function(self, T, one_str):
result = []
for i in T:
get_states = self.move_function(i, one_str)
if get_states == None:
continue
else:
for i in get_states:
result.append(i)
if len(result) == 0:
return None
else:
return result
def get_closure(self, T):
result = []
my_stack = []
for t in T:
result.append(t)
my_stack.append(t)
while len(my_stack) is not 0:
state = my_stack[0]
my_stack.pop(0)
next_states = self.move_function(state, "&")
if next_states is not None:
for u in next_states:
if u not in result:
result.append(u)
my_stack.append(u)
# 因为result里最少也有传入的参数T，所以不会返回None
return result
def nfa_to_dfa(self):
# dfa的状态集
dfa_states = []
# 代表dfa_states中的状态数量
count = 0
# 存放未标记过的状态
no_mark_states = []
# 首先把nfa初始状态的闭包加进未标记状态集
no_mark_states.append(self.get_closure([self.s]))
# 把nfa初始状态的闭包当作nfa的初始状态
dfa_s = self.get_closure([self.s])
# 取出所有非空的输入集 ps:因为后面要去除&字符，所以这里使用深拷贝，不会影响my_inputs的值
dfa_inputs = copy.deepcopy(self.my_inputs)
# 去除输入集中的&（空）
dfa_inputs.remove("&")
# dfa的状态转换集
dfa_move = []
while len(no_mark_states) is not 0:
# 存放待会需要加入未标记状态集的状态
wait_state = []
# 遍历未标记的状态集。当循环执行完毕，未标记状态集清空，把代加入未标记状态集的状态加入no_mark_states中
for i in no_mark_states:
# 把当前状态加入dfa的状态集，数量+1
dfa_states.append(i)
count = count + 1
# 代表当前状态的转换集
current_move = []
# 对于每一个没空输入字符，计算dfa的下一状态
for j in dfa_inputs:
smove_result = self.smove_function(i, j)
if smove_result is not None:
next_states = self.get_closure(smove_result)
if next_states is not None:
# 在dfa的状态转换集中加入转换
current_move.append({j: next_states})
if next_states not in dfa_states:
wait_state.append(next_states)
# 把当前状态的状态转换集加入dfa的状态转换集
dfa_move.append(current_move)
# 清空未标记状态集
no_mark_states = []
# 将待加入未标记状态集的状态加入未标记状态集
for i in wait_state:
no_mark_states.append(i)
# dfa的终态集
dfa_e = []
for i in dfa_states:
if self.e in i:
dfa_e.append(i)
dfa = DFA(dfa_states, dfa_inputs, dfa_move, dfa_s, dfa_e)
return dfa
class DFA:
# 初始化函数，传入状态集、输入集、转移函数集、初态、终态
def __init__(self, states, my_inputs, move, s, e):
self.states = states
self.my_inputs = my_inputs
self.move = move
self.s = s
self.e = e
def to_string(self):
print("==================")
print("该DFA的状态集如下：")
count = 0
for i in self.states:
count = count + 1
if count == len(self.states):
print(i)
else:
print(i, end=",")
print("==================")
print("该DFA的输入字符如下：")
count = 0
for i in self.my_inputs:
count = count + 1
if count == len(self.my_inputs):
print(i)
else:
print(i, end=",")
print("==================")
print("该DFA的状态转换如下：")
count = 0
for i in self.move:
print("状态" + str(count) + "：", end="")
count = count + 1
count_1 = 0
for j in i:
count_1 = count_1 + 1
if count_1 == len(i):
print(str(self.states[count-1]) + "->" + str(list(j.values())[0]))
else:
print(str(self.states[count-1]) + "->" + str(list(j.values())[0]), end=" ")
print("==================")
print("该DFA的初态：")
count = 0
print(self.s)
print("==================")
print("该DFA的终态：")
count = 0
for i in self.e:
count = count + 1
if count == len(self.e):
print(i)
else:
print(i, end=",")
if __name__ == "__main__":
with open("my_input.txt", 'r') as f:
text_list = f.readlines()
states_number = int(input("请输入状态的总数量(如有四个状态，则状态集为0，1，2，3)："))
states_number = int(text_list[0])
states = []
my_input = input("请输入输入集：")
my_input = text_list[1].replace("\n", "")
my_inputs = []
result = my_input.split(',')
for i in result:
my_inputs.append(i)
move = []
for i in range(0, states_number):
states.append(i)
states_move = input("请输入" + str(i+1) + "状态的状态转移情况，如0状态遇到空会转移到1和2状态，就输入&-1|&-2：")
states_move = text_list[i+2].replace("\n", "")
all_moves = states_move.split("|")
list_1 = []
for j in all_moves:
result = j.split("-")
if len(result) == 2:
dict_1 = {result[0]: result[1]}
else:
print("no")
dict_1 = {}
list_1.append(dict_1)
move.append(list_1)
s = int(input("请输入初态："))
s = int(text_list[13])
e = int(input("请输入终态："))
e = int(text_list[14])
nfa = NFA(states, my_inputs, move, s, e)
dfa = nfa.nfa_to_dfa()
dfa.to_string()运行结果
输入信息：
NFA输入信息输出：
得到的DFA信息：
