一、试验名称
不确定有穷状态自动机的确定化
二、试验目标
输出：非确定有穷状态自动机 NFA
输入：确定化的有穷状态自动机 DFA
三、试验原理
1、NFA 定义
一个不确定的有穷自动机 M 是一个五元组，M=(K,E,f,S,Z) 其中
a. K 是一个有穷集，它的每个元素称为一个状态；
b. E 是一个有穷字母表，它的每个元素称为一个输出符号；
c. f 是一个从 K×E 到 K 的子集的映像，即：KE*->2k，其中 2k 示意 K 的幂集；
d. S 蕴含于 K，是一个非空初态集；
e. Z 蕴含于 K，是一个终态集。
2、DFA 的定义
一个确定的有穷自动机 M 是一个五元组，M=(K,E,f,S,Z) 其中
a. K 是一个有穷集，它的每个元素称为一个状态；
b. E 是一个有穷字母表，它的每个元素称为一个输出符号；
c. f 是转换函数，是 K×E->K 上的映像，即，如 f(ki,a)=kj(ki∈K,kj∈K) 就意味着，以后状态为 ki，输出字符为 a 时，将转换到下一状态 kj，咱们把 kj 称作 ki 的一个后继状态；
d. S∈K，是惟一的一个初态；
e. Z 蕴含于 K，是一个终态集，终态也称可承受状态或完结状态。
3、closure 函数
状态汇合 I 的 ε—闭包，示意为 ε—closure(I)，定义为一状态集，是状态集 I 中的任何状态 S 经任意条 ε 弧而能达到的状态的汇合。
4、move 函数
状态汇合 I 的 a 弧转换，示意为 move(I,a)，定义为状态汇合 J，其中 J 是所有那些从 I 中的某一状态通过一条 a 弧而达到的状态的整体。
四、试验思路
本次试验采纳 python 实现。
1、输出
依据课本 NFA 的定义，输出五元组，顺次输出状态集、输出符号、初态集、终态集以及映像，将这些别离存入五个列表中。其中对于映像的输出格局：先输出状态一，再输出输出符号，最初输出状态二，一次输出一条弧。
2、closure 算法
定义 closure 函数模式为 closure(a,f)，其中，a 为要做 closure 闭包的状态汇合，f 为 NFA 的映像的汇合。具体思维为：
a. 设立一个最终返回后果的列表 b，初值与列表 a 相等。设立一个空列表 s，用于寄存每次 closure 闭包新退出的状态。
b. 执行 while 循环，此循环判断条件为 1，即会始终执行上来，直到遇到 closure 闭包没有新增状态的时候执行完结。
c. 对 a 中的每一个状态求 closure 闭包，即判断 f 中状态一等于 a 中状态的弧，再判断 f 中该状态的弧是否为 ε（具体代码中用’$’代替），若是，则将该弧的状态二退出 s 中。
d. 判断 s 是否为空，若为空则阐明此次循环没有新增状态，即阐明 closure 闭包在上一次循环时已执行结束，输入上次循环的后果 b。若 s 不为空，阐明本次循环依然有新增状态，则将新增状态退出 b 中，并且将新增的状态汇合赋值给 a，以新增的状态集持续做循环判断，直到某次循环 s 为空完结。
3、move 算法
move 算法的核心思想与 closure 算法统一，其函数模式为 move(a,e,f)，其中 e 为 move 算法 move(I,a) 的 a。move 算法只需要求从状态汇合中某一状态通过一条 a 弧而达到的状态整体，所以不须要进行 while 循环执行屡次，只需执行 closure 算法中 c 步骤一次即可。
4、结构子集
建设两个列表 C1、C2，其中 C1 用于寄存最终的状态集，C2 作为标记应用，对应 C1 中的子集，若 C1 中的子集也进行了 closure 闭包则 C2 中相应元素标记为 1，否则为 0。具体思维为：
a. 首先对初态集进行 closure 闭包，存于 C1 中，C2 的第一个元素赋值为 0。
b. 标记 C2 第一个元素为 1，对 C1 中第一个汇合先做 move 算法再做 closure 算法，若其中一个算法得出空集合则间接返回空列表，否则判断 C1 中是否有该状态集，若无则退出 C1 中，C2 中相应元素赋值为 0，示意未标记。
c. 反复执行 b 步骤，直到 C2 中所有元素为 1，示意标记结束，执行实现，所失去 C1 为最终状态子集。
5、输入
采纳矩阵模式输入，C1 中每个状态汇合的下标为最终合并后的状态。
五、试验小结
本次试验次要遇到了以下问题：
1、输出存储问题
若依据课本模式应输出 M =(K,E,f,S,Z)，再对 f 进行开展，尽管用算法实现这一模式不难，然而对于后续的操作不太不便，所以最终抉择了顺次输入五元组，别离存于五个列表中。
2、closure 算法问题
最后想用递归的思维实现 closure 算法，即每次进行一步 closure 闭包，返回后果为新失去的状态集的 closure 闭包，然而对于递归完结的判断条件以及参数的传递不太明确，所以最终没有抉择递归，而是抉择了死循环外面加上退出循环条件的模式实现。
3、输入问题
输入的模式最终没有实现 DFA 的状态图而是应用矩阵的模式输入，问题在于对于以状态汇合为结点结构状态图这样的图形模式方面的常识不理解，最终以矩阵模式输入。
通过本次试验，对于 NFA 转换为 DFA 的过程有了粗浅的意识，对于 closure 算法和 move 算法的思维十分分明。
六、附件
1、源代码
K = [] # 状态
E = [] # 符号
f = [] # 弧
S = [] # 初态
Z = [] # 终态
# 输出
a = input('输出状态 ( 以空格辨别, 以换行完结):')
K = a.split(' ')
a = input('输出输出符号 ( 以空格辨别, 以换行完结):')
E = a.split(' ')
a = input('输出初态 ( 以空格辨别, 以换行完结):')
S = a.split(' ')
a = input('输出终态 ( 以空格辨别, 以换行完结):')
Z = a.split(' ')
print('输出弧的条数:')
n = int(input())
print('输出弧 ( 别离输出状态 1, 输出符号, 状态 2, 以空格辨别换行完结,ε 示意为 $)')
for i in range(n):
f.append([])
a = input()
f[len(f)-1] = a.split(' ')
# closure 算法
def closure(a, f): # a 为列表
b = a
while 1:
s = []
for i in a:
for j in range(len(f)):
if i == f[j][0] and f[j][1] == '$':
s.append(f[j][2])
if len(s) == 0:
break
else:
for i in s:
b.append(i)
a = s
return sorted(b)
# move 算法
def move(a, e, f): # a 为列表 e 为一个符号
s = []
for i in a:
for j in range(len(f)):
if i == f[j][0] and f[j][1] == e:
s.append(f[j][2])
return sorted(s)
# 算出最终子集
C1 = [] # C1 为最终子集
C2 = []
C1.append(closure(S, f))
C2.append(0)
while C2.pop(len(C2)-1) == 0:
C2.append(0)
for i in range(len(C1)):
if C2[i] == 0:
C2[i] = 1
for j in E:
A = move(C1[i], j, f)
if A == []:
break
B = closure(A, f)
if B == []:
break
k = 0
for m in C1:
if B == m:
k = k+1
if k == 0:
C1.append(B)
C2.append(0)
print('输入 NFA 结构的子集:')
print(C1)
print('输入 DFA:')
print('S', end=' ')
for x in E:
print(x, end=' ')
print('\n')
# 输入 DFA
for i in range(len(C1)):
print(i, end=' ')
for j in E:
a1 = move(C1[i], j, f)
if a1 == []:
print(a1, end=' ')
continue
a2 = closure(a1, f)
if a2 == []:
print(a2, end=' ')
continue
for k in range(len(C1)):
if C1[k] == a2:
print(k, end=' ')
break
y = 0 # 判断子集中是否有终态
for m in Z:
if m in C1[i]:
y = y+1
if y == 0:
print(0)
else:
print(1)
print('\n')2、程序输入后果