自动机:DFA转化为正则表达式

我们知道,正则表达式描述的是一类满足特殊规则的字符串,这些字符串构成的集合我们称之为语言。而 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 允许经过所有状态的正则表达式。

相关文章

Loading Likes...

发表评论

电子邮件地址不会被公开。 必填项已用*标注