思考题的引入
首先看这样一道思考题：
如何用正则表达式识别所有是三的倍数的二进制串？
考虑最暴力的做法。用一个变量rem表示一个串的前缀作为二进制对3的余数，对新进来的字符讨论：
- 进来一个
0，则rem=(rem<<1)%3;，因为我们是从高位向低位读的 - 进来一个
1，则rem=((rem<<1)+1)%3
那么只需要判断最终rem是否为0就好了
自动机的做法
在做这题之前，可以先想想这样的一个问题：
如何用自动机识别所有是三的倍数的二进制串？
或者说
如何用自动机表示上述暴力做法？
注意到rem的取值只能为0,1,2，因此可以建3个点，每个点两条出边表示对不同字符的处理转移，那么建出来的图如下
其中节点1,2,3分别表示rem对应为0,1,2的状态。
"但是问题还没完啊，你不是要正则表达式吗"
做到这一点需要一些前置姿势
正则表达式代数
没错！正则表达式也是有代数结构的！
为了方便，我们规定连接运算(concatenation)用.符号表示
| 符号 | 性质 |
|---|---|
| | | 结合律，交换律，对.的分配率 |
| . | 结合律 |
| ^ | 幂等律 |
它们的优先级从上到下递增
那么自然应该想到，列出正则表达式的代数方程，也是可以解方程的
Arden's Theorem
定理的内容很简单，即对于形如 (x=A|xB) 的方程，(x) 的解都是 (AB^*) 的形式
对解的长度进行归纳。当 (n=1)， (x_1=A) 是原方程的一个解，满足 (x=AB^*) 的形式
设当 (n<k) 时成立，则 (x_{n-1}=Aoverbrace{Bldots B}^{n-1 ext{个}B})，带入方程右侧就有 (x_n=x_{n-1}B=Aoverbrace{Bldots B}^{n ext{个}B})
由数学归纳法可知原方程的解都是 (x=AB^*) 的形式，并且容易验证形如 (AB^*) 的串都是方程的解。
类似的也有对 (x=A|Bx) 的结论
自动机到正则表达式的转换
我们知道，自动机的每个状态都对应着一个接受串的集合(从初始状态到当前状态所有路径组成的串的并)，而不同状态之间存在转移关系
那么就可以设未知数列方程辣！
对于最开始的那个DFA，我们可以设它的三个状态对应的接受串的正则表达式为(x_0,x_1,x_2)，那么有如下关系
对式3用Arden's Theorem得到(x_2=x_101^*)
代入式2得到 (x_1=x_01|x_101^*0=x_01(01^*0)^*)
代入式1得到 (x_0=x_00|x_01(01^*0)^*=x_0(0|1(01^*0)^*)=(0|1(01^*0)^*)^*)
于是就得到了与该自动机等价的正则表达式
需要注意的是，在这个表达式中，我们认为可以有任意的前缀零，并且空串和任意长度的0串都是3的倍数
升华一下
如果你乐于思考，就会发现我们上述"消元"过程意味着什么——我们在化简自动机的状态！
也就是说，假如我们要求得表示DFA从起点到终点e的串的集合的正则表达式，那么我们只需要合并掉除起点和e以外的所有状态即可。