从正则表达式到NFA
正则表达式
定义 : 正则表达式可以描述所有通过对某个字母表上的符号应用并、连接、闭包运算而得到的语言；可以用正则表达式定义的语言叫做正则集合
性质 : 如果两个正则表达式 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
对于只有字符\( a \)表达式，构造如下的NFA
运算封闭：
并运算
设正则文法 L 和 G，如下
\( L(x) = \{ x^{1} \} \)
\( G(y) = \{ y^{1} \} \)
并运算后的的NFA表达式 记为 \( M = (L \cup G) \)，则有\( M(z) = \{z | z \in L 或 z \in G\} \)
连接运算
沿用上面的文法，设\( M = (LG) \)，则有\( \{z = xy | x \in L 且 y \in G \} \)，得到如下图
闭包运算
沿用上面记号文法\( M=\{z^{n} | z \in L 且 n \in N^{0}\} \)