> ## Content Index
> Fetch the complete content index at: https://blog.hacking.pub/llms.txt
> Use this file to discover other available public pages before exploring further.

# 子集构造法
- URL: https://blog.hacking.pub/2017/05/05/zi-ji-gou-zao-fa/
- Published: 2017-05-05T06:09:45.000Z
- Updated: 2018-08-06T08:04:33.000Z
- Author: chainhelen
- Tags: 自动机, DFA, NFA, 子集构造

#### 概念

首先介绍一下 有限自动机 FA （Finite Automate）的概念，形式上它是一个五元组 \\( (S, \\sum, \\delta, s\_0, S\_A) \\)

1. \\( S \\) 是识别器的有限状态集，以及一个错误状态\\( S\_e\\)
2. \\( \\sum \\)是识别器使用的有限字母表。通常，\\( \\sum \\) 是转移图中边的标签合集
3. \\( \\delta(s, c) \\)是识别器的转移函数。它将每个状态 \\(s \\in S \\)和每个字符\\(c \\in \\sum \\)映射到下一个状态。在状态\\( s\_i \\)遇到输入字符\\(c\\)，FA将采取\\(s\_i \\rightarrow^c \\delta(s\_i, c)\\)
4. \\(s\_0 \\in S\\) 是制定的起始状态
5. \\( S\_A \\) 是接受状态的集合，\\(S\_A \\subseteq S\\)，通常在转移表中为双层圆圈

`NFA`是不确定有穷自动机（Nondeterministic Finite Automata）  
`DFA`是确定有穷自动机（deterministic finite automaton ）  
`正则表达式`  
这三者是等价的，本文要讲的是NFA -> DFA的转化

#### 区别

NFA和DFA最大的区别就是NFA允许输入\\( \\epsilon \\)进行转移，其状态对同一字符输入有可能多种转移

#### 子集构造

###### 1.DFA的状态集

首先先定义几个概念

1. `edge`  
\\(edge(s, c)\\)表示从状态\\(s\\)沿着字符c可以到达的所有NFA状态的集合
2. `closoure`(闭包)  
对于状态集合\\( S \\)，\\( clousre(S)\\)是从\\(S\\)状态触发，无需接受任何字符，只沿\\( \\epsilon \\)边就可以到达的状态组成的集合。求闭包的算法如下

$$  
\\begin{matrix}  
T \\leftarrow S \\\\  
repeat & T^{'} \\leftarrow T \\\\  
& T \\leftarrow T^{'} \\cup (\\cup\_{s \\in T^{'}}edge(s, \\epsilon )) \\tag{公式1} \\\\  
until & T = T^{'}\\\\  
\\end{matrix}  
$$

依据这个我们就可以构造出对应DFA的状态集:  
对于NFA某个状态集合d出发，输入c，所能到达的状态集合并记为\\( DFAedge(d, c)\\)，具体表达式如下:  
$$ DFAedge(d, c) = closure(\\cup\_{s \\in d}edge(s, c)) \\tag{公式2} $$

这里是通过原有的`NFA一些状态集`构造新的`DFA状态`的算法过程  
真实NFA -> DFA的 构造过程的算法公式比较繁琐，但跟数学归纳法类似，直接通过下面例子说明

###### 2.起始项

上面部分讲的是中间递推过程，例子里面需要的是`起始项`  
也就是DFA的起始状态，设为\\( DFA\\\_s\_0 \\)，记NFA的起始状态为\\( NFA\\\_s\_0 \\)，那么

$$ DFA\\\_s\_0 = closure( NFA \\\_s\_0 ) \\tag{公式3} $$

###### 3.例子

拿装配脑袋的文章例子说明

![1.png](https://blog.hacking.pub/qiniu/%E5%AD%90%E9%9B%86%E6%9E%84%E9%80%A0%E6%B3%95/1.png)

`起始项`  
\\( NFA \\\_s\_0 = { S\_{\[1\]} } \\)  
\\( DFA\\\_s\_0 = closure( NFA \\\_s\_0 ) = closure({ S\_{\[1\]} } ) \\)  
由于\\( edge(S\_{\[1\]}, \\epsilon ) = \\{S\_{\[1\]} , S\_{\[4\]}, S\_{\[9\]}, S\_{\[14\]} \\}\\)  
满足 `公式1`中 \\( T = T^{'} \\)，故而\\( DFA\\\_s\_0 = \\{S\_{\[1\]} , S\_{\[4\]}, S\_{\[9\]}, S\_{\[14\]} \\} \\)

`递推过程`  
对于状态  
\\( DFA\\\_s\_0 = \\{S\_{\[1\]} , S\_{\[4\]}, S\_{\[9\]}, S\_{\[14\]} \\} \\)，如何求出另一个转移函数和状态  
就从转移字符`i`来说，看`公式2`  
此时有\\( d = \\{S\_{\[1\]} , S\_{\[4\]}, S\_{\[9\]}, S\_{\[14\]} \\}, c = 'i' \\)  
那么 \\( \\cup\_{s \\in d}edge(s, c) = \\{ S\_{\[2\]}, S\_{\[5\]}, S\_{\[15\]}\\} \\)，继续求\\( closure(\\{S\_{\[2\]}, S\_{\[5\]}, S\_{\[15\]}\\}) = \\{ S\_{\[2\]}, S\_{\[5\]}, S\_{\[15\]}, S\_{\[8\]}, S\_{\[6\]} \\} \\)  
所以新的DFA的\\( \\delta(DFA\\\_s\_{0}, 'i') = \\{ S\_{\[2\]}, S\_{\[5\]}, S\_{\[15\]}, S\_{\[8\]}, S\_{\[6\]} \\} \\)  
如下图

![2.png](https://blog.hacking.pub/qiniu/%E5%AD%90%E9%9B%86%E6%9E%84%E9%80%A0%E6%B3%95/2.png)

#### 其他

`公式2` 支持分配律\\( DFAedge(d, c) = closure(\\cup\_{s \\in d}edge(s, c)) = \\cup\_{s \\in d}(closure(edge(s, c))) \\)

---

#### 参考

[自己动手开发编译器（三）有穷自动机](http://www.cnblogs.com/Ninputer/archive/2011/06/10/2077991.html?ref=blog.hacking.pub)