前言
写这篇文章的时候，代码已经全忘了，因为是半年前的代码,(代码1000%原创，只是因为当时赶时间，写的很烂),
但是对于正规式到最小化DFA，只要思路在，就能写出来，所以本文章不详细解释代码，只谈思路,代码的实现主要看如何去设计类，NFA到DFA的思路都是统一的，但是看网上讲的思路大多不是特别全，这里非常详细的介绍
当然，展示必不可少
(下面的伪代码是真的伪，不过能看懂就行了)
在线小demo
语法检测
作为一个优质的toC作品，必然要好好考虑代码的健壮性，所以必须要对用户输入的正规式进行检测
我做的工作有:
# 首先判断每个字符是否在下面的列表里,字母表只能使用a-z的单个字符,否则比较麻烦,
# 当然也可以用多个字符做一层映射，如aa对应a,反正最底层还是要去拿单个字符去转化
["(",")","|","*","a","b"......."z"]
# 其次进行括号匹配，也就是一个简单的栈，不满足直接返回false
# 初始括号数为0，遍历正规式遇到"("，括号数+1，遇到")"，括号数-1，最后若括号数==0，则满足要求
# 再其次是对一些无意义的操作符号组合进行判断，若有返回false，4种操作符按顺序两两搭配，有7种无意义的组合，如
["()","(|".....]正规式转NFA
这个思路是我从0想的，原理不难，与书上大同小异，但是我这个有更细致的思想
作为递归老选手，一上来就知道要对整个转化步骤进行一个普通化，（肯定有专业名词，但是我不清楚）
也就是挖掘每个步骤相同的步骤，并且找出结束递归的条件
首先，先告诉大家，所有子函数都会返回两个结点，头结点和尾结点
子函数1
分|:
首先，我们拿到一个正规式，这个正规式有无穷的可能，
但是一开始的形式一定是形如 ....|....|..... 或者 .....
也就是说，一个正规式一定可以拆成一个或多个正规式，
对，这句话没有问题，反正一个正规式绝对可以拆成一个正规式，没毛病啊
当然，其实我要表达的是，将整个正规式按最外层|进行分割
问题1：如何确定|不是在括号内部?
非常简单，同样是括号栈，当且仅当目前的符号为|,且此时括号栈数字为0时,满足可以分割条件
此时记录下分割位置，继续找，直到找到所有的分割点为止，最后分割为多个正规式
问题2：如何将分割好的正规式连起来?
非常简单，大家都是或连起来的，就一个并联嘛，
定义一个头结点和尾结点，最终连成这样
问题3：连接的具体操作是什么，怎么把头结点链接到每个子节点?
记得上面说过的，每个子函数都会返回一个头结点和尾结点
那么就让当前头结点链接所以子头结点，所以子尾结点连接当前尾结点
问题4：函数的返回值是什么?
当然是上面定义的头结点和尾结点
那么最终，我们得到了我们的第一个函数，大概思路是这样
将正规式按外层拆分成多个子正规式
头结点 = node()
尾结点 = node()
for item in 子正规式列表：
子头，子尾 = 子函数2(item)
头结点.next.append('ε', 子头)
子尾.next.append('ε', 尾结点)
return 头结点,尾结点看起来非常清晰明了对不对？
子函数2
分():
此时我们明确知道当前的正规式最外层不可能有|，（有也怪子函数1,这样分工明确）
就假装子函数1已经100%正确
那么此时的正规式一定是由四种元素组成的 a a (...) (....)
括号内部可能还有|，但是不影响，只管当前最外层
对于四种元素，那么有如下策略
单个a或者a*看起来虽然已经最简，但是我们任然不考虑，任然把它当做一个整体,让子函数3去考虑
最终四种策略如下
或许有人发现a和(...) a和(...)的策略是一样的
问题1：如何链接每个子正规式?
这里每次子元素都新生成两个结点，同时更新总的尾结点，像串麻花一样串起来
像下面这个样子，最终返回总的头结点和尾结点
虽然看起来多了很多结点，但是这样逻辑更加分明了
问题2：a和(...)以及a和(...)都交给子函数3去做吗?
当然不是了，这里就是我们的递归点了，
对于a和a*：
我们将a传递给子函数3来解决
对于(...)和(...)*:
我们将...内容交给子函数1解决，这里的...可能非常非常复杂,是由好多好多个|分开且到处都是*,但是已经影响不到当前这一层了
问题3：如何将原正规式分成四种基本类型?
我的解决方案是这样，还是括号栈
每次检索一个正规式的字符，进行括号栈的出入栈，（就是加减法进行模拟）
每当括号站值为0，判断当前字符是否为")",判断下一个字符是否为*
这个时候四种情况就出来了，对不对？
那么最终，我们得到了我们的第二个函数，大概思路是这样
将正规式分为四种基本元素形如 a a* (...) (...)* 并按顺序放入子正规式列表
当前头结点 = node()
当前尾结点 = 当前头结点
for item in 子正规式列表：
新头 = node()
新尾 = node()
if type(item) == type(a): #即属于第一类
子头，子尾 = 子函数3(item)
新头.next.append('ε', 子头)
子尾.next.append('ε', 新尾)
当前尾结点.next.append('ε', 新头)
当前尾结点 = 新尾
if type(item) == type(a*): #即属于第二类
子头，子尾 = 子函数3(item[:-1])
新头.next.append('ε', 子头)
新头.next.append('ε', 新尾)
新尾.next.append('ε', 新头)
子尾.next.append('ε', 新尾)
当前尾结点.next.append('ε', 新头)
当前尾结点 = 新尾
if type(item) == type((...)): #即属于第三类
子头，子尾 = 子函数1(item[1:-1])
新头.next.append('ε', 子头)
子尾.next.append('ε', 新尾)
当前尾结点.next.append('ε', 新头)
当前尾结点 = 新尾
if type(item) == type((...)*): #即属于第四类
子头，子尾 = 子函数1(item[1:-2])
新头.next.append('ε', 子头)
新头.next.append('ε', 新尾)
新尾.next.append('ε', 新头)
子尾.next.append('ε', 新尾)
当前尾结点.next.append('ε', 新头)
当前尾结点 = 新尾
return 当前头结点,当前尾结点看起来也是非常清晰明了对不对？
（策略图中几条线，这里就append几下）
什么？写的太长了不清晰？ok我们简化一下
将正规式分为四种基本元素形如 a a* (...) (...)* 并按顺序放入子正规式列表
当前头结点 = node()
当前尾结点 = 当前头结点
for item in 子正规式列表：
新头 = node()
新尾 = node()
type = type(item)
if type == type(a): #即属于第一类
子头，子尾 = 子函数3(item)
elif type == type(a*):
子头，子尾 = 子函数3(item[:-1])
新头.next.append('ε', 新尾)
新尾.next.append('ε', 新头)
elif type == type((...)):
子头，子尾 = 子函数3(item[1:-1])
else:
新头.next.append('ε', 新尾)
新尾.next.append('ε', 新头)
子头，子尾 = 子函数3(item[1:-2])
新头.next.append('ε', 子头)
子尾.next.append('ε', 新尾)
当前尾结点.next.append('ε', 新头)
当前尾结点 = 新尾
return 当前头结点,当前尾结点其实也就是稍微精简了一下
子函数3
到这里，这个函数永远得到的都是形如a这样的单个正规式
那么策略如下
返回头尾结点
那么最终，我们得到了我们的第三个函数，大概思路是这样
头结点 = node()
尾结点 = node()
头结点.next.append("a",尾结点) #这里的a只是象征意义
return 头结点,尾结点到此为止就是我们的正规式转NFA的算法，思路是不是特别清晰
当然用代码实现起来还是有那么一点点复杂,最终整个函数返回的start和end就是我们整个NFA的头尾
最后别忘了把返回的start标记为开始结点，end标记为结束结点
class NFA(object):
operator = ['(', ')', '|', '*', '+']
def __init__(self):
self.S = []
self.alphabet = []
self.S0 = []
self.Z = []
allnodes.append(self)
def normaltype_transform_NFA_1(self, NT):
str = []
for i in NT:
if i not in self.operator:
str.append(i)
str = list(set(str))
self.alphabet = str
a, b = self.normaltype_transform_NFA_2(NT)
return a, b
def return_x(self, x):
for i in self.S:
if i.name == x:
return i
def normaltype_transform_NFA_2(self, NT):
b = Node([], [])
a = Node([], [])
self.S.append(a)
self.S.append(b)
or_location = []
for i in range(len(NT)):
if NT[i] == '|' and self.judge_or_location(NT, i):
or_location.append(i)
son_Nt = []
start_iloc = 0
for i in range(len(or_location)):
son_Nt.append(NT[start_iloc:or_location[i]])
start_iloc = or_location[i]+1
son_Nt.append(NT[start_iloc:])
if len(son_Nt) != 1:
for i in son_Nt:
start, end = self.normaltype_transform_NFA_3(i)
a.nextnode.append([start.name, "null"])
end.nextnode.append([b.name, "null"])
elif not re.findall(r"\(", son_Nt[0]):
start, end = self.normaltype_transform_NFA_3(son_Nt[0])
a.nextnode.append([start.name, "null"])
end.nextnode.append([b.name, "null"])
else:
start, end = self.normaltype_transform_NFA_3(son_Nt[0])
a.nextnode.append([start.name, "null"])
end.nextnode.append([b.name, "null"])
return a, b
def normaltype_transform_NFA_3(self, NT):
c = 1
d = 1
kuo = []
son_Nt = []
i = 0
start = 0
while i < len(NT):
if NT[i] == '(':
kuo.append('(')
if NT[i] == ')':
kuo.pop()
if len(kuo) == 0:
if i+1 < len(NT) and NT[i+1] == '*':
son_Nt.append(NT[start:i+2])
start = i+2
i += 2
continue
else:
son_Nt.append(NT[start:i+1])
start = i+1
i += 1
continue
i += 1
for s_nt in son_Nt:
if s_nt[0] != '(':
if s_nt[-1] == '*':
start, end = self.normaltype_transform_NFA_4(s_nt[:-1])
if d != 1:
d.nextnode.append([start.name, "null"])
start.nextnode.append([end.name, "null"])
end.nextnode.append([start.name, "null"])
if c == 1:
c = start
d = end
else:
start, end = self.normaltype_transform_NFA_4(s_nt)
if d != 1:
d.nextnode.append([start.name, "null"])
if c == 1:
c = start
d = end
if s_nt[0] == '(':
if s_nt[-1] == '*':
start, end = self.normaltype_transform_NFA_2(s_nt[1:-2])
if d != 1:
d.nextnode.append([start.name, "null"])
start.nextnode.append([end.name, "null"])
end.nextnode.append([start.name, "null"])
if c == 1:
c = start
d = end
else:
start, end = self.normaltype_transform_NFA_2(s_nt[1:-1])
if d != 1:
d.nextnode.append([start.name, "null"])
if c == 1:
c = start
d = end
return c, d
def normaltype_transform_NFA_4(self, NT):
e = Node([], [])
f = Node(nextnode=[[e.name, NT[0]]])
self.S.append(f)
self.S.append(e)
return f, e
def judge_or_location(self, NT, x):
left_kuo = 0
reght_kuo = 0
for i in range(x):
if NT[i] == '(':
left_kuo += 1
if NT[i] == ')':
reght_kuo += 1
if left_kuo == reght_kuo:
return True
else:
return False
a = NFA()
start, end = a.normaltype_transform_NFA_1(normaltype)
start.is_beginnode = True
end.is_terminator = True
a.S0.append(start)
a.Z.append(end)当然我的代码写的看起来像shi一样，是因为这是半年前写的，而且当时为了赶进度，6个小时构思加实现的
现在也懒得重新写了，
NFA转DFA
这个算法就是经典算法了，子集构造法，这边推荐一篇网上的博客
NFA到DFA的转化
写的非常好，但我感觉还是不那么接地气
为了更加方便理解，采用循序渐进的方法，我们再重新梳理一遍
我们先只求开始结点的ɛ闭包
结点的闭包是指 结点通过ɛ（空串）达到的所有结点，那么这些达到结点和本结点共同组成一个集合，这个集合就是该节点的ɛ闭包,多个结点的闭包就是取集合的并集
比如结点5的闭包
比如结点3,8的闭包
因为开始结点可以通过空串到达，显然这些结点可以归为同一个开始结点，且DFA是不允许有ɛ路径的
（只要新出现的闭包与已有的闭包完全的等价，就用原来的名字来取代，否则视为新的闭包，重新取名字）
把这个闭包当做开始结点
ε_closure(0)={0,1,2,4,7}=A此时我们就用更加通俗易懂的话语来阐述
现在我们就有一个个闭包了，是开始结点A
现在，我们对A进行考察，看看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现在我们就有三个闭包了，分别是A,B,C
闭包A通过a到达B，闭包A通过b到达C
现在，我们对B和C进行考察，看看B和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现在我们发现BC新到达的四个闭包里，只有一个是新的与ABC不同的，所以我们取名为D
现在我们就有四个闭包了，分别是A,B,C,D
闭包A通过a到达B，闭包A通过b到达C,闭包B通过a到达B，闭包B通过b到达D,闭包C通过a到达B，闭包C通过b到达C
此时再对D进行考察,看看D能到达的闭包
结果是这样
ε_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到这里我们发现没有出现新的闭包了，那么必然这些闭包已经包括NFA所有的结点（因为NFA是连通图）
现在我们我们还是有四个闭包，分别是A,B,C,D
闭包A通过a到达B，闭包A通过b到达C,闭包B通过a到达B，闭包B通过b到达D,闭包C通过a到达B，闭包C通过b到达C,闭包D通过a到达B，闭包D通过b到达C
到这里就结束NFA到DFA的转化，结果我们会发现，在新构造的四个结点ABCD中，每个结点通过状态a或b到达的结点都是唯一确定的，这也就是DFA的确定性
了解原理之后，我们便开始设计我们的伪代码（真的伪）
求空闭包(结点):
return 包含 结点的空闭包集合 的一个类
求到达闭包(结点，状态):
新闭包 = []
for 结点 in 结点通过状态到达的结点:
新闭包 = 新闭包 U 求空闭包(结点)
return 新闭包
子函数1():
闭包队列 = []
A = 求空闭包(开始结点)
闭包队列.append(A)
while(闭包队列 != []):
待求闭包 = 闭包队列[0]
闭包队列 = 闭包队列[1:] #这里模拟队列弹出队首元素
for 状态 in 状态集合: # 就是字符集，对于上面的例子就是[a,b]
新闭包 = 求到达闭包(待求闭包，状态)
待求闭包.next.append(状态,新闭包) #
if 新闭包与之前的闭包不同:
闭包队列.append(新闭包)
return A是不是看起来非常简洁明了，真实代码写起来还是稍微复杂
class DFA(object):
def __init__(self):
self.S = []
self.alphabet = []
self.S0 = []
self.Z = []
allnodes.append(self)
def NFA_transform_DFA_1(self, nfa):
start_set = []
all_start_set = nfa.S0[0].nextnode
stackk = nfa.S0[0].nextnode
while stackk:
if stackk[0][9] == "null" and stackk[0][0] not in start_set:
start_set.append(stackk[0][0])
for i in nfa.return_x(stackk[0][0]).nextnode:
if i not in all_start_set:
all_start_set.append(i)
stackk.append(i)
stackk = stackk[1:]
set_stack = []
node1 = DFAnode()
node1.data = start_set
node1.is_beginnode = True
self.S.append(node1)
self.S0.append(node1)
set_stack.append(node1)
while len(set_stack) > 0:
for i in nfa.alphabet:
new_set = []
for nod in set_stack[0].data: # nod = X,1,2,3
nodd = nfa.return_x(nod)
for next_node in nodd.nextnode:
if next_node[1] == i and next_node[0] not in new_set:
new_set.append(next_node[0])
self.NFA_transform_DFA_2(
new_set, nfa, next_node[0])
if new_set:
self.appendd(i, set_stack, new_set)
set_stack = set_stack[1:] # 模拟队列弹出首项
for i in self.S:
for j in i.data:
if j == nfa.Z[0].name: # 包含结束状态
i.is_terminator = True
def NFA_transform_DFA_2(self, new_set, nfa, next_node):
next_node = nfa.return_x(next_node)
for i in next_node.nextnode:
if i[1] == 'null' and i[0] not in new_set:
new_set.append(i[0])
self.NFA_transform_DFA_2(new_set, nfa, i[0])
return True
def appendd(self, str, a, b):
for i in self.S:
if len(i.data) == len(b):
j = 0
while j < len(i.data):
if i.data[j] not in b:
break
else:
j += 1
if j == len(i.data):
# 有
a[0].nextnode.append([i.name, str])
return False
else:
continue
node2 = DFAnode()
node2.data = b
a[0].nextnode.append([node2.name, str])
a.append(node2)
self.S.append(node2)
return True
b = DFA()
b.NFA_transform_DFA_1(a) #a是第一问的NFA()类
b.alphabet = a.alphabetDFA最小化
这个是我最近写的，之前上课只完成到DFA部分
最小化原理也非常简单
第一步求出俩集合，非终结符和终结符的集合（嗯好像串了）
搞错了，再来，终止状态集合和非终止状态集合
对所有集合进行考察，看是否集合内所有结点都能够通过某状态到达同一个集合
说的比较抽象，而且有很多误导性，这里的同一个集合是指当前状态下的集合，比如，一开始只有两个集合，划分了之后，集合就会变得更多，每次判定都是判定的当前状态的集合
举个例子
目前有两个集合，称之为A和B，（左A右B）
此时对我们两集合进行考察：
对于A：
0 -a-> A 0 -b-> A
1 -a-> A 1 -b-> A
2 -a-> A 2 -b-> A
3 -a-> A 3 -b-> B
4 -a-> A 4 -b-> A
5 -b-> B完全一样的才能合为一类，3,5是不能合并的！！！
我们可以暂时将其分为3类
对于B：
就一个结点不可再分，就是B
所以可以看出，当集合内就剩一个结点，也是终止条件
此时我们有了如下四个集合
A:{0,1,2,4},B:{3},C:{5},D:{6}此时大家也知道只需要考虑第一个集合,且此时
0 -a-> A 0 -b-> A
1 -a-> B 1 -b-> A
2 -a-> C 2 -b-> A
4 -a-> A 4 -b-> A那么现在就变成了
A:{0,4},B:{1},C:{2},D:{3},E:{5},F:{6}再进一步考察
0 -a-> B 0 -b-> C
4 -a-> B 4 -b-> C不需要再分，结果就出来了
大家可以看到这个分集合的过程，会不断的新增名字，所以名字的顺序我这个算法无法得到顺序保证，但是结果对就行
注意，如何确定开始结点和结束结点？
因为一开始就把结束结点划分为一类，所以含有结束结点的集合全部为结束结点，而含有开始结点的集合就为开始结点，一定只有一个
真的伪的伪代码如下:
判断所有集合是否都满足要求(集合列表):
for 集合 in 集合列表:
if not (集合结点数为1 或 集合内所有结点通过任意状态到达的集合相同)
return true
return fasle
考察集合():
将集合按 到达集合 进行拆分
拆分的集合添加到集合列表
子函数1():
A,B = 划分终止状态集合和非终止状态集合()
集合列表 = [A,B]
while(判断所有集合是否都满足要求(集合列表))
for 集合 in 集合列表: # 每次都必须重新检查整个列表，因为随着集合列表的变化，原来的满足条件的集合也可能不满相同的达到集合
考察集合(集合，集合列表)看起来是不是非常简洁明了
添加到集合列表的时候出了好多好多bug，主要是因为，for循环内就对集合列表进行了更新，这种巨复杂，最好是，for循环完毕再对集合列表进行一次更新，然后再判断，再更新
为了解决这个bug，我来了画龙点睛的一笔，我让考察集合函数返回true或false，代表是否拆分，若一旦拆分，直接break整个for循环，然后再进一步判断，妙极，用提高时间复杂度来 降低代码复杂度，我真是天才（才不是为了偷懒），
真实代码
def keyinonenoed(nodelist, a, b):
for i in nodelist:
if a in i.data and b in i.data:
return True
return False
def judge2(newitem, nodelist):
nextnode = newitem.node[0].nextnode
if not nextnode:
for item in newitem.node:
if item.nextnode:
return False
else:
for item in newitem.node[1:]:
if len(item.nextnode) != len(nextnode):
return False
for key in nextnode:
if key not in item.nextnode:
return False
if not keyinonenoed(
nodelist, nextnode[key], item.nextnode[key]):
return False
return True
def judge_is_over(nodelist):
ll = 0
for newitem in nodelist:
if judge2(newitem, nodelist):
ll += 1
if ll == len(nodelist):
return True
else:
return False
def chaifen(nodelist):
tmp = []
for newitem in nodelist:
removetmp = []
if len(newitem.node) == 1:
continue
if not judge2(newitem, nodelist):
first_node = newitem.node[0]
newsnode = simpleDFAnode()
newsnode.data.append(first_node.name)
newsnode.node.append(first_node)
removetmp.append(first_node)
for node in newitem.node:
lenn = 0
if len(node.nextnode) != len(first_node.nextnode):
continue
for key in node.nextnode:
if key not in first_node.nextnode:
break
if not keyinonenoed(
nodelist, node.nextnode[key], first_node.nextnode[key]):
break
lenn += 1
if lenn == len(node.nextnode) and node.name != first_node.name:
newsnode.data.append(node.name)
newsnode.node.append(node)
removetmp.append(node)
tmp.append(newsnode)
for rem in removetmp:
newitem.data.remove(rem.name)
newitem.node.remove(rem)
if removetmp: # 神来之笔
break
nodelist.extend(tmp)
def DFA_to_simpleDFA(S):
start = simpleDFAnode()
end = simpleDFAnode()
nodelist = []
for i in S:
if i.is_terminator:
end.data.append(i.name)
end.node.append(i)
else:
start.data.append(i.name)
start.node.append(i)
if len(start.data) != 0:
nodelist.append(start)
nodelist.append(end)
else:
nodelist.append(end)
while not judge_is_over(nodelist):
chaifen(nodelist)
return nodelist
def returnsdfa(nodelist, index):
for i in nodelist:
if index in i.data:
return i.name
for item in b.S:
tmp = {}
for i in item.nextnode:
tmp[i[1]] = i[0]
item.nextnode = tmp
nodelist = DFA_to_simpleDFA(b.S)
for node in nodelist:
for i in node.node[0].nextnode:
node.nextnode[i] = returnsdfa(nodelist, node.node[0].nextnode[i])
for i in nodelist:
for j in i.node:
if j.is_terminator:
i.is_terminator = True
if j.is_beginnode:
i.is_beginnode = True这代码看着都难受，要是有哪位大佬能好心帮忙改改就好了
除此之外，获得结果后，我还用了graphviz这个软件进行绘图
难度不大，直接看官方文档就能看懂，建议大家都多看原生的官方文档，网上的各种教程真的，，一言难尽
graphviz
以上就是正规式转NFA转DFA转最小化DFA（python实现）的全部内容，只是我新网站的一块内容
完整代码
要是觉得有用，去github给我整个网站项目点个小星星吧！！！！
我要去点星星
完结撒花✿✿ヽ(°▽°)ノ✿
