# DFA与NFA

## 有限状态机

计算理论中有限状态机的定义：

> 有限状态机是一个五元组 (Q, Σ ,δ, q0, F)：
>
> * Q 是一个有穷集合，叫 **状态集**
> * Σ 是一个有穷集合，叫 **字母表**
> * δ : Q × Σ → Q 是 **转移函数**
> * q0 ∈ Q 是 **起始状态**.
> * F ⊆ Q是 **接受状态**

![](https://2676543305-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LiOHdMI5BLLQcx3U7Ro%2F-LkbZxypKqudP-LY49tt%2F-Lkba1kUE1E29Y1dhput%2Fimage.png?alt=media\&token=28742176-cba3-4507-a75d-7f9bb6e1d971)

根据上图状态机，直观描述如下：

* 开始状态：圆圈表示状态，被一个“没有起点的箭头”指向的状态，是开始状态，上例中是q1
* 接受状态：图中用双圆圈表示，上例
* 输入：在一个状态下，向状态机输入的符号/信号，不同输入导致状态机产生不同的状态改变，上例中的0/1即为输入符号
* 转移：在一个状态下，根据特定输入，改变到特定状态的过程，就是转移

因此有限状态机的工作过程，就是从开始状态，根据不同的输入，自动进行状态转移的过程，直到进入接受状态为止

> 正则表达式，可以认为是对一组字符串集合的描述。有限状态机也可以用来描述字符串集合

上图状态机描述的字符串集合，如下所示：

```
01
011
0111
0100
0101
01100
……
```

因此正则表达式，可使用有限状态机来实现。正则表达式匹配字符串的过程，可以分解为：

* 正则表达式转换为等价的有限状态机
* 字符串输入有限状态机执行

## 确定有限状态自动机（DFA）

DFA的每一个状态对于字母表中的每一个符号总是恰好有一个转移箭头射出。其确定性在于，在一个状态下，输入一个符号，一定是转移到确定的状态，没有其他的可能性

![](https://2676543305-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LiOHdMI5BLLQcx3U7Ro%2F-LkbZxypKqudP-LY49tt%2F-Lkbv3rSwh3NVaDrE7KR%2Fimage.png?alt=media\&token=e069fe5d-f3dd-44c4-a59d-db053c2163ff)

如上图确定有限状态自动机，任何一个状态下输入一个符号，总是确定性的进入到另一个状态

## 非确定有限状态自动机（NFA）

NFA中每一个状态对于字母表的每一个符号（如：0/1）可能有多个箭头射出。其不确定性在于，在一个状态下，输入一个符号，可能转移到n个状态，出现了多种状态转移。另外NFA中箭头的标号可以是 ε（空转移，即：未输入任何符号也可转移到另一个状态），而DFA不允许

![](https://2676543305-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LiOHdMI5BLLQcx3U7Ro%2F-LkbZxypKqudP-LY49tt%2F-Lkbws9YuGHvKtr0WUQe%2Fimage.png?alt=media\&token=fe59b62c-afe6-4e57-91b1-004a9cf63fc4)

如上图非确定有限状态自动机，当对q1状态输入1时，可能转移到q2状态或停留在当前状态

> 每一台 NFA 都有一台等价的 DFA与之对应

NFA分解为DFA的过程如下：

* 非确定性可以看做若干“过程”能同时运行的一类并行计算，当NFA分头跟踪若干选择 时，这对应于一个过程分叉成若干个子过程，各子过程分别进行，如果这些子过程中至少有一个接受，那么整个计算接受
* 把非确定性计算看作一颗可能性的树，树根对应计算的开始，树中的每一个分支点对应计算中机器有多种选择的点，如果计算分支中至少有一个结束在接受状态，则机器接受

![](https://2676543305-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LiOHdMI5BLLQcx3U7Ro%2F-LkbZxypKqudP-LY49tt%2F-LkbzMsybOXXFj5P4cdS%2Fimage.png?alt=media\&token=deca8f68-cb82-455b-bc1f-ff10cf0f442a)

但NFA转换为DFA的过程，会消耗更多资源，最终得到的DFA要占用大量的存储空间。另外DFA相比NFA在实现一些正则表达式时会更复杂。因此大都编程语言，使用NFA正则引擎

## NFA中回溯

从上文可知，NFA的不确定性在于，在一个状态下，输入一个符号，可能转移到n个状态，出现了多种状态转移。在模式匹配时，转移到了其中一个状态进行匹配，最终匹配失败；此时要回到之前的状态再尝试其它路径，这个回退状态就是**“回溯”**

正则表达式匹配字符串的这种方式，有个学名，叫回溯法。百度百科定义：

> 从问题的某一种状态（初始状态）出发，搜索从这种状态出发所能达到的所有“状态”，当一条路走到“尽头”的时候（不能再前进），再后退一步或若干步，从另一种可能“状态”出发，继续搜索，直到所有的“路径”（状态）都试探过。这种不断“前进”、不断“回溯”寻找解的方法，就称作“回溯法”

### 匹配回溯

举例，说明回溯现象。如正则`/ab{1,3}c/`，其可视化形式：

![](https://2676543305-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LiOHdMI5BLLQcx3U7Ro%2F-Lkc-qWL6Z7nBSF2fXcT%2F-Lkc6M1iFPljlTfo6zt4%2Fimage.png?alt=media\&token=3baca7a3-1f25-43ed-a4af-3a81e06035fe)

输入匹配字符串`abbc`，匹配过程如下：

![](https://2676543305-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LiOHdMI5BLLQcx3U7Ro%2F-Lkc-qWL6Z7nBSF2fXcT%2F-Lkc6twnKkIt6X9Gcfhj%2Fimage.png?alt=media\&token=5a7f15e7-7418-4e41-9395-b0c220eb4a17)

图中第5步有红颜色，表示匹配不成功。此时b{1,3}已经匹配到了2个字符“b”，准备尝试第三个时，结果发现接下来的字符是“c”。那么就认为b{1,3}就已经匹配完毕。然后状态又回到之前的状态（即第6步，与第4步一样），最后再用子表达式c，去匹配字符“c”。

其中第6个步骤，就是“回溯”

### 常见的回溯形式

* **贪婪量词**

如上述例子，b{1,3}是贪婪的**，**匹配时尝试可能的顺序是从多往少的方向去尝试。首先会尝试"bbb"，然后再看整个正则是否能匹配。不能匹配时，吐出一个"b"，即在"bb"的基础上，再继续尝试。如果还不行，再吐出一个，再试。

```javascript
var string = "12345";

var regex = /(\d{1,3})(\d{1,3})/;
console.log( string.match(regex) );
// => ["12345", "123", "45", index: 0, input: "12345"]
```

其中，前面的\d{1,3}匹配的是"123"，后面的\d{1,3}匹配的是"45"

* **惰性量词**

惰性量词就是在贪婪量词后面加个问号。表示尽可能少的匹配

```javascript
var string = "12345";
var regex = /(\d{1,3}?)(\d{1,3})/;
console.log( string.match(regex) );
// => ["1234", "1", "234", index: 0, input: "12345"]
```

其中\d{1,3}?只匹配到一个字符"1"，而后面的\d{1,3}匹配了"234"

* **分支结构**

分支也是惰性的，比如`/abc|abc123/`，去匹配字符串`abc123`，得到的结果是`abc`，因为分支会一个一个尝试，如果前面的满足了，后面就不会再尝试

```javascript
var string = "abc123";
var regex = /abc|abc123/;
console.log( string.match(regex) );
// => ["abc", index: 0, input: "abc123", groups: undefined]
```