我们知道，正则表达式描述的是一类满足特殊规则的字符串，这些字符串构成的集合我们称之为语言。而 DFA 也是用于描述语言的一种方式，它可以转化为等价的正则表达式，从而恰好接受属于这个 DFA 对应的语言。
对于整个 DFA 而言，有着对应的正则表达式，而对于其中的某两个状态而言，它们之间的路径也有着对应的正则表达式。为什么这么说？因为两个状态之间的路径也是某类满足特殊规则的字符串，我们同样可以用正则表达式来表示它们。
因此，要把一个 DFA 转化为正则表达式，我们可以通过将它分解为更简单的子问题来迭代求解：
- 将状态按 1、2、...、n 的顺序依次标号
- 先求任意状态 i 到 j（i 可以等于 j，即自身到自身），不经过其它状态的路径对应的正则表达式
- 求状态 i 到 j，最高只经过状态 1 的路径对应的正则表达式
- 求状态 i 到 j，最高只经过状态 2 的路径对应的正则表达式
- 依此类推……
- 求状态 i 到 j，最高只经过状态 n 的路径对应的正则表达式，即经过所有状态的路径对应的正则表达式
什么是从 i 到 j 最高只经过状态 k 的路径？它表示的是我们可以选择性地经过状态1、状态2、……、状态 k 之间的任意状态，但不能经过状态 K+1、K+2 等高于状态 k 的那些状态。
为了便于说明情况，我简单画了下图。如果最高只经过状态 k-1，那么 i 到 j 就没有路径可以到达。从图中可以看出，当最高只经过状态 k 时，那么 i 到 j 可以经过 i+1、i+2、……、k-1、k 从而到达状态 j，路径表示为 $a_i a_{i+1} \cdots a_{k-1} a_k^\prime$。
同理，当最高只经过状态 k+1 时，那么除了经过状态 k 直接到达状态 j，还可以先经过 k 再经过 k+1 到达状态 j，路径表示为 $a_i a_{i+1} \cdots a_{k-1} a_k a_{k+1}$，如下图所示。
我们可以用一个表达式来描述从状态 i 到 j ，最高只经过状态 k 的路径对应的正则表达式：
$$R_{ij}^{(k)} = R_{ij}^{(k-1)} + R_{ik}^{(k-1)} (R_{kk}^{(k-1)})^* R_{kj}^{(k-1)}$$
上面这个表达式看似复杂，但只要理解了它的原理就很简单了。
我们可以将从 i 到 j 最高只经过状态 k 的路径分为两种：
- 根本不经过状态 k
- 经过状态 k 至少一次
此时再来看上述表达式，前一项 $R_{ij}^{(k-1)}$ 表示不经过状态 k 的路径对应的正则表达式，后一项表示经过了状态 k 至少一次的路径对应的正则表达式。前一项很容易理解，因为不经过状态 k ，相当于最高只经过了 k-1，所以直接用 $R_{ij}^{(k-1)}$ 来表示。而后一项可以拆分成三部分：先从 i 到 k，然后在 k 这个状态上可以再经过任意次（自身到自身），最后从 k 到 j，如下图所示。
注意下图中的情况。如果状态 j 有到自身的环（这里是字符c），那么从其它状态到 j 的路径中若包含了这个环，则属于经过状态 j 的情况。也就是说，只有经过的最高状态大于等于 j 时，这个环才能计算在内。例如下图中 i 到 j 最高只经过状态 j-1 时，对应的正则表达式 $R_{ij}^{(j-1)}=ab$，而 $R_{ij}^{(j)}=abc^*$。
同样的道理也适用于自身到自身的情况，例如从状态 j 到自身，通过一次路径 c 就属于不经过任何状态的情况，但如果要多次通过路径 c，就属于经过状态 j 的情况，需要当前能经过的最高状态大于等于 j 才可以。即 $R_{jj}^{(j-1)}=ε+c$ ， $R_{jj}^{(j)}=ε+c^*=c^*$ 。这里的 ε 表示输入为空也可到达自身，每一个状态自身到自身的正则表达式都包含 ε。
下面是一个正则表达式计算的示例，这里只给出化简后的结果，具体步骤请自行计算。
首先计算 k=0 的情况，即不经过其它状态：
$R_{11}^{(0)}=ε+1$
$R_{12}^{(0)}=0$
$R_{21}^{(0)}=\varnothing$
$R_{22}^{(0)}=ε+0+1$
计算 k=1 的情况，即最高只经过状态1：
$R_{11}^{(1)}=1^*$
$R_{12}^{(1)}=1^*0$
$R_{21}^{(1)}=\varnothing$
$R_{22}^{(1)}=ε+0+1$
计算 k=2 的情况，这个示例中即经过所有状态：
$R_{11}^{(2)}=1^*$
$R_{12}^{(2)}=1^*0(0+1)^*$
$R_{21}^{(2)}=\varnothing$
$R_{22}^{(2)}=(0+1)^*$
实际上，要将该 DFA 转化为正则表达式，最后 k=2 的情况只需计算一个 $R_{12}^{(2)}$ 即可，该表达式就是整个 DFA 对应的表达式，即状态 1 到状态 2 允许经过所有状态的正则表达式。
作者：Wray Zheng
原文：http://www.codebelief.com/article/2017/11/automata-convert-dfa-to-regular-expression/
