一、试验名称
不确定有穷状态自动机的确定化
二、试验目标
输出：非确定有穷状态自动机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、程序输入后果
发表回复