NFA转DFA的子集构造(Subset Construction)算法详解

目录

@(NFA转DFA的子集构造Subset Construction算法)

之前学习编译原理的时候老师有讲过子集构造法,当时我以为自己听懂了,信心满满。可是这两天我做了一些题目,发现自己实际上还是太嫩了,学习浮于表面。之后又重新看了龙书和虎书,对子集构造法有了更深层次的了解。特此发出一篇文章分享我的经验。

1 概念

概念是我们学习编译原理的重中之重,虽然他很晦涩难懂,但我有必要将其放在最开始。

1.1 虎书概念

虎书的概念更偏向于理论化,我当时看的时候一头雾水,但是不要担心,之后会一点一点解释的

首先,我们形式化定义\(\epsilon\)闭包如下:

  • \(edge(s,c)\):状态\(s\)沿着标有\(c\)的边可到达的所有NFA状态的集合;
  • \(closure(S)\): 对于状态集合\(S\),从\(S\)出发,只通过\(\epsilon\)边可以达到的状态集合;
    • 这种经过\(\epsilon\)边的概念可以用数学方法表述,即\(closure(S)\)是满足如下条件的最小集合\(T\):
      \(T=S \cup \left( \bigcup_{s \in T}edge(s,\epsilon) \right)\)
    • 我们可以用迭代法来算出\(T\):
      \(T \leftarrow S \\ repeat \ T' \leftarrow T \\ \qquad \quad T \leftarrow T' \cup \left( \bigcup_{s \in T'}edge(s,\epsilon) \right) \\ until \ T=T'\)

      解释一下:当我们位于一个状态集合\(S\),\(S\)里任意状态经过若干\(\epsilon\)能够到达的状态,都将包含在 \(closure(S)\) 里。

  • 龙书里将这个操作定义为\(\epsilon-closure(T)\)(\(T\)为状态集合)。

现在,假设我们位于由NFA状态\(s_i,s_k,s_l\)组成的集合\(d= \lbrace s_i,s_k,s_l \rbrace\)中。从\(d\)中的状态出发,输入符号\(c\),将到达NFA新的状态集;我们称这个状态集为\(DFAedge(d,c)\):

  • \(DFAedge(d,c)=closure \left( \bigcup_{s \in d}edge(s,c) \right)\)

    解释一下:将遍历集合\(d\)中的所有状态,得到 \(d\) 关于\(T=edge(s,c)\)的状态集,并对 \(T\) 求 \(closure(T)\),得到的即为\(DFAedge(d,c)\)。简而言之,就是从一个状态集,经过一个输入到达的状态集为 \(T'=DFAedge(d,c)\)。

利用\(DFAedge\)能更形式化地写出NFA模拟算法。如果初态是\(s_1\),输入字符串是\(c_1,...,c_k\),则算法为:

  • \(d \leftarrow closure( \lbrace s_1 \rbrace ) \\ for \ i \leftarrow 1 \ to \ k \\ \quad d \leftarrow DFAedge(d,c_i)\)

有了\(closure\)和\(DFAedge\)算法,就能构造出DFADFA的状态\(d_1\)就是\(closure(s_1)\)。抽象而言,如果\(d_j=DFAedge(d_i,c)\)则存在一条从 \(d_i\) 到 \(d_j\) 的标记为 \(c\) 的边。令 \(\Sigma\) 是字母表:

  • \(states[0] \leftarrow \lbrace \rbrace; \qquad states[1] \leftarrow closure(\lbrace s_1 \rbrace) \\ p\leftarrow 1; \qquad j \leftarrow 0 \\ while \ j \leq p \\ \ \ \ foreach \ c \in \Sigma \\ \qquad e \leftarrow DFAedge(states[j],c) \\ \qquad if \ e =states[i] \ for \ some \ i \leq p \\ \qquad \quad \ then \ trans[j,c] \leftarrow i \\ \qquad \quad \ else \ p \leftarrow p+1 \\ \qquad \qquad \quad \, states[p] \leftarrow e \\ \qquad \qquad \quad \, trans[j,c] \leftarrow p \\ \; \; j \leftarrow j+1\)

    解释一下:\(state[]\)代表了最终DFA的一个状态所对应的NFA状态集,\(s_1\)为初始状态,\(closure(\lbrace s_1 \rbrace)\)代表了初始状态\(s_1\)的闭包。上文中的代码实际上和龙书的代码一个意思,龙书的代码更加简单直白,所以这里可以跳过。等看完下面的龙书再回头来看

1.2 龙书概念

个人认为龙书的概念更加通俗易懂,但是由于没有数学公式的归纳,导致理论基础不扎实,有点慌。所以推荐两本书一起看。

首先,是概念:

  • 子集构造法的基本思想是让构造得到的DFA的每个状态对应NFA的一个状态集合。DFA在读入\(a_1a_2...a_n\)之后到达的状态应该对应于相应的NFA从开始状态出发,沿着以\(a_1a_2...a_n\)为边的路径能达到的状态的集合。

    解释一下:概念很直观哈,我就不解释了^_^

接着,是算法:

  • 输入:一个NFA N
  • 输出:一个接受同样语言的DFA D
  • 方法:我们为算法 D 构造一个转换表\(Dtran\)。D的每个状态是一个NFA集合,构造\(Dtran\),使得 D “并行地”模拟 N 在遇到一个给定输入串可能执行的所有动作。下面我们给出一些函数的定义
操作 描述
\(\epsilon - closure(s)\) 能够从NFA状态\(s\)开始只通过\(\epsilon\)转换到达的NFA状态集合
\(\epsilon - closure(T)\) 能够从\(T\)中某个NFA状态\(s\)开始只通过\(\epsilon\)转换到达的NFA状态集合,即 \(\bigcup_{s \in T} \epsilon -closure(s)\)
\(move(T,a)\) 能够从 \(T\) 中某个状态 \(s\) 出发通过标号为 \(a\) 的转换到达的NFA状态的集合
  • 在读入第一个符号之前,N可以位于集合\(\epsilon-closure(s_0)\)中的任何状态上 ,其中,\(s_0\)是 N 的开始状态。
  • 下面进行回归纳:假定N在读入输入串\(x\)之后可以位于集合T的任意状态上。如果下一个输入符号是 \(a\),那么N可以立即移动到集合\(move(T,a)\)中的任何状态。然而,N 可以读入\(a\)之后再执行几个\(\epsilon\)转换,因此 N 在读入\(xa\)之后可以位于\(\epsilon-closure(move(T,a))\)中的任意状态上。接着我们可以构造出转换函数\(Dtran\):
    • 一开始,\(\epsilon-clusure(s_0)\)是\(Dstates\)的唯一状态,且它未标记(请注意,“标记”是非常重要的概念)
    • \(while(在Dstates中有一个未标记的状态T) \lbrace \\ \quad \quad \ 给T加上标记; \\ \quad \quad \ for(每个输入符号a) \lbrace \\ \qquad \qquad \quad U=\epsilon-clusure\left(move(T,a) \right) \\ \qquad \qquad \quad if(U不在Dstates中) \\ \qquad \qquad \qquad \qquad \, 将U加入Dstates中,且不加标记; \\ \qquad \qquad \quad Dtran[T,a]=U \\ \quad \quad \ \rbrace \\ \rbrace\)

      解释一下:这部分代码和虎书上的代码意思相近,这个更好理解。算法里的\(Dtran[T,a]=\epsilon-clusure\left(move(T,a) \right)\)每个\(Dtran[T,a]\)都可能是DFA的一个状态。

2 举个例子解释

  • 题目:给定一个正则表达式\((a|b)^*abb\)的NFA,我们使用子集构造法构造DFA
    NFA转DFA的子集构造(Subset Construction)算法详解
  • 解法:首先,我们分析得出,NFA的初始为状态0。因而初始状态集\(A=\epsilon-closure(0)=\lbrace0,1,2,4,7 \rbrace\)。
    1. \(A\)被加上标记,对于输入符号\(a,b\),分别求出:
      \(a:B=\epsilon-closure(move(A,a))=\lbrace1,2,3,4,6,7,8 \rbrace \\b:C=\epsilon-closure(move(A,b))=\lbrace1,2,4,5,6,7 \rbrace\)
    2. \(B,C\)都没有被标记,因而将\(B,C\)依次加上标记,对于输入符号\(a,b\),分别求出:
      \(a:B=\epsilon-closure(move(B,a))=\lbrace1,2,3,4,6,7,8 \rbrace \\b:D=\epsilon-closure(move(B,b))=\lbrace1,2,4,5,6,7,9 \rbrace\)
      \(a:B=\epsilon-closure(move(C,a))=\lbrace1,2,3,4,6,7,8 \rbrace \\b:C=\epsilon-closure(move(C,b))=\lbrace1,2,4,5,6,7 \rbrace\)
    3. 现在只剩\(D\)没有加标记,因而给\(D\)加上标记,对于输入符号\(a,b\),分别求出:
      \(a:B=\epsilon-closure(move(D,a))=\lbrace1,2,3,4,6,7,8 \rbrace \\b:E=\epsilon-closure(move(D,b))=\lbrace1,2,4,5,6,7,10 \rbrace\)
    4. 还剩一个\(E\)没有标记,因而给\(E\)加上标记,对于输入符号\(a,b\),分别求出:
      \(a:B=\epsilon-closure(move(E,a))=\lbrace1,2,3,4,6,7,8 \rbrace \\b:C=\epsilon-closure(move(E,b))=\lbrace1,2,4,5,6,7 \rbrace\)
    5. 所有构造出来的集合都已经被标记,构造完成!\(A,B,C,D,E\)为五个不同状态:
      \(A=\lbrace0,1,2,4,7 \rbrace \\ B=\lbrace1,2,3,4,6,7,8 \rbrace \\ C=\lbrace1,2,4,5,6,7 \rbrace \\ D=\lbrace1,2,4,5,6,7,9 \rbrace \\ E=\lbrace1,2,4,5,6,7,10 \rbrace\)
    6. 接着就是根据状态来画图了,最好先画好状态表:
      NFA转DFA的子集构造(Subset Construction)算法详解

解释一下:由此可知,\(A\)通过\(a\),连到\(B\),以此类推。就可以做出DFA图了^_^NFA转DFA的子集构造(Subset Construction)算法详解

3 如何最小化DFA的状态数量

很简单,如果开始于\(s_1\)的机器接收字符串\(\sigma\),始于\(s_2\)的和始于与\(s_1\)接收的串相同并到达相同状态,且两个状态集同为终态或者非终态,那么\(s_1,s_2\)是等价的。我们可以把指向\(s_2\)的连线全部指向\(s_1\),并删除\(s_2\),反之亦然。

  • 举个书上的例子:
    NFA转DFA的子集构造(Subset Construction)算法详解
  • 图中的\(\lbrace 5,6,8,15 \rbrace,\lbrace 6,7,8 \rbrace\)是等价的,还有\(\lbrace 10,11,13,15 \rbrace,\lbrace 11,12,13 \rbrace\)也是等价的。

    Tips:在判断是否等价前,我们要先判断是否为死状态哦(1.不能到达终态 2.从开始没有路径指向这个状态)。

4 总结

NFADFA知识总结就到这里,有什么问题请留言,有错误请批评指正,非常感谢您的阅读。

上一篇:mysql – 其唯一目的是指定另一个表的子集的表


下一篇:[LeetCode] (medium) 416. Partition Equal Subset Sum