> ## 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.

# 从正则表达式到NFA
- URL: https://blog.hacking.pub/2017/05/09/cong-zheng-ze-biao-da-shi-dao-nfa/
- Published: 2017-05-09T08:34:53.000Z
- Updated: 2020-08-24T13:55:48.000Z
- Author: chainhelen
- Tags: NFA, DFA, 正则表达, 正则表达式, Thompson算法

#### 正则表达式

`定义` : 正则表达式可以描述所有通过对某个字母表上的符号应用`并`、`连接`、`闭包`运算而得到的语言；可以用正则表达式定义的语言叫做`正则集合`

`性质` : 如果两个正则表达式 r 和 s 表示同样的语言，则称 r 和 s等价  
遵循一些代数性质

| 定律                                         | 描述                       |          |
| ------------------------------------------ | ------------------------ | -------- |
| \\( r \| s = s                             | r \\)                    | \| 是可以交换 |
| \\( r\|(s|t) = (r|s)|t \\)                 | \| 是可结合的                 |          |
| \\( r(st) = (rs)t \\)                      | 连接是可结合的                  |          |
| \\( r(s\|t)=rs|rt \\)；\\( (s|t)r=sr|tr \\) | 连接对\|是可分配的               |          |
| \\( \\epsilon r=r\\epsilon =r \\)          | \\(\\epsilon\\)是连接的单位元   |          |
| \\( r^{\*} = (r\|\\epsilon)^{\*} \\)       | 闭包中一定包含\\( \\epsilon \\) |          |
| \\( r^{\*\*} = r^{\*} \\)                  | \* 具有幂等性                 |          |

#### NFA

`有穷自动机`是识别器(recognizer)，它能对每一个可能的输入串简单地回答“是”或者“否”  
在上一篇也讲过自动机其实是5元组，这里不重复说了

#### Thompson算法

（以下部分均来源于龙书第四版）

算法转化分为两步，一个是正则基本表达式，第二个是基本表达式的运算

`基本规则 :`  
对于 \\( \\epsilon \\) 表达式 ,构造如下的NFA

![7.png](https://blog.hacking.pub/qiniu/%E4%BB%8E%E6%AD%A3%E5%88%99%E8%A1%A8%E8%BE%BE%E5%BC%8F%E5%88%B0NFA/7.png)

对于只有字符\\( a \\)表达式，构造如下的NFA

![6.png](https://blog.hacking.pub/qiniu/%E4%BB%8E%E6%AD%A3%E5%88%99%E8%A1%A8%E8%BE%BE%E5%BC%8F%E5%88%B0NFA/6.png)

`运算封闭：`  
**并运算**

设正则文法 L 和 G，如下  
\\( L(x) = \\{ x^{1} \\} \\)

![8.png](https://blog.hacking.pub/qiniu/%E4%BB%8E%E6%AD%A3%E5%88%99%E8%A1%A8%E8%BE%BE%E5%BC%8F%E5%88%B0NFA/8.png)

\\( G(y) = \\{ y^{1} \\} \\)

![11.png](https://blog.hacking.pub/qiniu/%E4%BB%8E%E6%AD%A3%E5%88%99%E8%A1%A8%E8%BE%BE%E5%BC%8F%E5%88%B0NFA/11.png)

并运算后的的NFA表达式 记为 \\( M = (L \\cup G) \\)，则有\\( M(z) = \\{z | z \\in L 或 z \\in G\\} \\)

![13.png](https://blog.hacking.pub/qiniu/%E4%BB%8E%E6%AD%A3%E5%88%99%E8%A1%A8%E8%BE%BE%E5%BC%8F%E5%88%B0NFA/13.png)

**连接运算**  
沿用上面的文法，设\\( M = (LG) \\)，则有\\( \\{z = xy | x \\in L 且 y \\in G \\} \\)，得到如下图

![16.png](https://blog.hacking.pub/qiniu/%E4%BB%8E%E6%AD%A3%E5%88%99%E8%A1%A8%E8%BE%BE%E5%BC%8F%E5%88%B0NFA/16.png)

**闭包运算**  
沿用上面记号文法\\( M=\\{z^{n} | z \\in L 且 n \\in N^{0}\\} \\)

![17.png](https://blog.hacking.pub/qiniu/%E4%BB%8E%E6%AD%A3%E5%88%99%E8%A1%A8%E8%BE%BE%E5%BC%8F%E5%88%B0NFA/17.png)

[下载visio文件](http://ogqj342jq.bkt.clouddn.com/%E4%BB%8E%E6%AD%A3%E5%88%99%E8%A1%A8%E8%BE%BE%E5%BC%8F%E5%88%B0NFA/%E4%BB%8E%E6%AD%A3%E5%88%99%E8%A1%A8%E8%BE%BE%E5%BC%8F%E5%88%B0NFA.vsdx?ref=blog.hacking.pub)