NFA与DFA的转换与优化

Compiler
"If it wasn't hard, everyone would do it. It's the hard that makes it great."
Tom Hanks
  1. 转换方法
  2. 实现

上一节《编译原理》课讲到了NFA（不确定的有穷自动机）向DFA（确定的有穷自动机）转换。考试要考，所以要手写变换过程，很繁琐，也很有趣。所以周末用python给实现了，并利用动态规划进行优化。

转换方法

这里主要涉及到对状态集合I的两个操作：

  1. 求ε-闭包。表示为ε-closure(I)，是指I中的任何状态S经过任意条ε弧能到达的状态的集合。
  2. 求I的α弧转换。表示为move(I,α)，是指I中某一状态经过一条α弧到达的状态的集合。

比如说这里有一个NFA N：

NFA

因为NFA是一个五元组，N=(K,E,f,S,Z),即为(状态集合，弧集合，转换集合，开始状态集合，终结状态集合)，所以由图可知：

NFA N = ({0,1,2,3,4,5,6,7,8,9,10},{a,b},f,{0},{10})，其中

  • f(0,ε) = {1}
  • f(1,ε) = {2,4}
  • f(2,a) = {3}
  • f(3,ε) = {6}
  • f(4,b) = {5}
  • f(5,ε) = {6}
  • f(6,ε) = {1,7}
  • f{7,a} = {8}
  • f(8,b) = {9}
  • f(9,b) = {10}

那么ε-closure(0)={0,1,2,4,7}

move({0,1,2,4,7},a) = {3,8}

ε-closure({3,8})={1,2,3,4,6,7,8}

可以借助表格来观察整个求解过程，每次求解后如果产生新集合，就会记录下来继续算，直到没有新集合为止。

T A=ε-closure(move(T,a)) B=ε-closure(move(T,b))
ε-closure(s)={0,1,2,4,7}=T0 {1,2,3,4,6,7,8}=T1 {1,2,4,5,6,7}=T2
T1 T1 {1,2,4,5,6,7,9}=T3
T2 T1 T2
T3 T1 {1,2,4,5,6,7,10}=T4
T4 T1 T2

此时T列下的集合{T0,T1,T2,T3,T4}就是DFA的状态，其中含有NFA初始状态的集合为DFA的初始状态（{T0}），含有NFA终结状态的集合为DFA的终结状态（{T4}）。

所以由NFA转换后的DFA为：

DFA

实现

首先是数据存储格式，使用json存储NFA的五元组：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
 
{
  "k" : ["0","1","2","3","4","5","6","7","8","9","10"],
  "e" : ["a","b"],
  "f" : {
    "0" : {
      "#" : ["1", "7"]
    },
    "1" : {
      "#" : ["2", "4"]
    },
    "2" : {
      "a" : ["3"]
    },
    "3" : {
      "#" : ["6"]
    },
    "4" : {
      "b" : ["5"]
    },
    "5" : {
      "#" : ["6"]
    },
    "6" : {
      "#" : ["1", "7"]
    },
    "7" : {
      "a" : ["8"]
    },
    "8" : {
      "b" : ["9"]
    },
    "9" : {
      "b" : ["10"]
    }
  },
  "s" : ["0"],
  "z" : ["10"]
}

读入时做了一些简单的判断，其实还可以做得更加周全，比如初始集s和终结集z是否被状态集k包含，等等。read()了之后就会把五元组包装返回。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 
def read(input):
  try:
    nfa = json.load(open(input,"r"))
    for i in nfa["f"]:
      if not i in nfa["k"]:
        raise Exception("Set f contains iterms that not belongs to set k.")
      for j in nfa["f"][i]:
        if not j in nfa["e"] and not j == '#':
          raise Exception("Set f contains iterms that not belongs to set e.")
    return (set(nfa["k"]), set(nfa["e"]), nfa["f"], set(nfa["s"]), set(nfa["z"]))
  except IOError:
    print "File no found!"
    sys.exit(1)
  except (KeyError, TypeError):
    print "Input data error!"
    sys.exit(1)
  except Exception, e:
    print(e.args[0])
    sys.exit(1)

使用creat_memo()接下来为计算创建缓存，因为计算闭包有大量的重复计算。memo是一个字典，以e集合（弧集合）的元素为键，每一个键对应的值也是一个字典，在计算闭包的过程中缓存该状态的闭包。（见closure()）

1
2
3
4
5
6
 
def creat_memo(e_set):
  memo = {}
  for i in e_set:
    memo[i] = {}
  memo['#'] = {}
  return memo

从文章开始时提到的转换方法很容易可以看到，两个操作有很大的相似性，所以我把它们封装成一个函数closure()了，调用时使用各自的接口。对应上面提到的弧转换操作，move()中的参数s和arc表示求move(s,arc)，而ph_closure()的arc默认为ε，这里用"#"表示。

1
2
3
4
5
 
def move(f, memo, s, arc):
  return closure(f, memo[arc], s, arc)

def ep_closure(f, memo, s):
  return closure(f, memo["#"], s, '#')

closure()是本程序的核心部分，当它接受了一个集合c_set时，会对c_set中的元素一一进行求闭包或者弧转换，再合并集合。在进行计算之前先查看缓存memo，看看之前有没有计算过，有就直接合并，没有就先计算出结果，在memo记录之后再进行合并。对于求闭包，因为是ε，所以每次要先包含本身，而弧转换则不需要。

注意memo[s] = set([s])，必须是set([s])不能是set(s),因为s为字符串，set(s)会把s中的每个字符都拆开。

接下来判断f转换中是否存在有关f(s,arc)的定义，存在的话：

  1. 闭包情况：深度优先递归的计算集合f(s,arc)的闭包，将它们合并回来。比如上面的NFA例子，一开始求ε-closure(0)的时候，发现f(0,ε)={1,7}，所以继续计算ε-closure(1)和ε-closure(7)。.....一直计算到尽头。每次递归计算过程中也会在memo上记录，所以整个计算过程会越来越快。
  2. 弧转换情况：由于弧只需要判断状态s的下个一个arc弧连接的状态，所以不需要递归，直接得出结果。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 
def closure(f, memo, c_set, arc):
  res = set()
  for s in c_set:
    if not s in memo:
      memo[s] = set()
      if arc == '#':
        #Attention here. Has to be a list
        memo[s] = set([s])
      if s in f:
        if arc in f[s]:
          if arc == '#':
            memo[s] |= closure(f, memo, set(f[s][arc]), arc)
          else:
            memo[s] = set(f[s][arc])
    res |= memo[s]
  return res

creat_dfa返回一个空的dfa结构，calc_dfa代表了上面提到的表格的运算过程，并把表格的内容保存到dfa结构中。先对初始状态集k求闭包，接下来为每个弧求弧转换闭包ε-closure(move(s, arc))。出现新集合就交给queue队列，并在dfa["k"]中做记录。我这里是利用集合在dfa["k"]中的index作为dfa状态的命名。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
 
def creat_dfa(e_set):
  dfa = {}
  dfa["k"] = []
  dfa["e"] = list(e_set)
  dfa["f"] = {}
  dfa["s"] = []
  dfa["z"] = []
  return dfa

def calc_dfa(k_set, e_set, f, s_set, z_set):
  dfa = creat_dfa(e_set)
  dfa_set = []
  memo = creat_memo(e_set)
  ep = ep_closure(f, memo, s_set)
  #Attention here. Has to be a list
  queue = deque([ep])

  dfa_set.append([ep])
  dfa["k"].append("0")
  dfa["s"].append("0")
  if not len(ep&z_set) == 0:
    dfa["z"].append("0")
  i = 0

  while queue:
    T = queue.popleft()
    j = ""
    index = str(i)
    i = i + 1
    dfa["f"][index] = {}
    for s in e_set:
      t = ep_closure(f, memo, move(f, memo, T, s))
      try:
        j = str(dfa_set.index(t))
      except ValueError:
        queue.append(t)
        j = str(len(dfa_set))
        dfa_set.append(t)
        dfa["k"].append(j)
      dfa["f"][index][s] = j
      if not len(t&s_set) == 0:
        dfa["s"].append(j)
      if not len(t&z_set) == 0:
        dfa["z"].append(j)

  return dfa

生成json的write_dfa和程序的其余代码：

1
2
3
4
5
6
7
8
9
10
11
12
 
def write_dfa(dfa, f):
  f = open(f, "w")
  f.write(json.dumps(dfa))
  f.close()

def main():
  (k_set, e_set, f, s_set, z_set) = read("NFA.json")
  dfa = calc_dfa(k_set, e_set, f, s_set, z_set)
  write_dfa(dfa, "DFA.json")
  

if __name__ == '__main__'

附上最后生成的json代码，就是上面的图DFA M

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
 
{
  "k": ["0", "1", "2", "3", "4"], 
  "z": ["4"], 
  "e": ["a", "b"], 
  "s": ["0"], 
  "f": {
    "1": {
      "a": "1", 
      "b": "3"
    }, 
    "0": {
      "a": "1", 
      "b": "2"
    }, 
    "3": {
      "a": "1", 
      "b": "4"
    }, 
    "2": {
      "a": "1", 
      "b": "2"
    }, 
    "4": {
      "a": "1", 
      "b": "2"
    }
  }
}

您还在局域网。 ——来自隔墙相望的评论