前言
写这篇文章的时候,代码已经全忘了,因为是半年前的代码,(代码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.alphabet
DFA最小化
这个是我最近写的,之前上课只完成到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给我整个网站项目点个小星星吧!!!!
我要去点星星
完结撒花✿✿ヽ(°▽°)ノ✿