使用状态消除法,可将中间状态替换为一个等效的正则表达式,重复此过程,即可完成转换。

常见的情况如下:

image-20210615212233179

一般性的情况如下:

image-20210615212422356

例子:

image-20210615212507595

马上上手做就会发现问题:这种带回环的怎么操作?

我们选择 $q_1$ 进行消除,先看作 $0^*$,进入它的是 $q2$ 和 $q0$,离开它的是 $q_2$。一共两种组合:

  1. $q_2\to q_1 \to q_2$:00*1
  2. $q_0\to q_1 \to q_2$:00*1

因此删除 $q_1$ 上的路径,添加上面两条路径:

image-20210615214619031

重复上述过程

image-20210615214901656

最终结果:

$$ 1*00*1(00*1 + 11*00*1)* $$

【例子】

image-20210626150250164

解:

对 q1 化简:

  • $q0\to q2$: bb*a
  • $q2\to q2$: bb*a

得:

image-20210626150443484

对 q2 化简:

  • $q0\to q0$: a*+bb*a(bb*a)*a

image-20210626150554383

答:RE 为 (a+bb*a (bb*a)*a)*

【例子】

image-20210626153114347

我们先添加辅助状态 $s,f$:

image-20210626153222177

分析 $q1$:来源有 $q0, q2$,去路有 $q0,q2,f$。将来源与去路的组合 分析如下:

途径 $q1$ 的路径 规则式
$q0\to q0$ aa
$q0\to q2$ ab
$q0\to f$ a
$q2\to q0$ aa
$q2\to q2$ ab
$q2\to f$ a

因此删除 q1,补充上述路径:

image-20210626153749559

分析 $q2$,来源有 $q0$,去路有 $q0, f$,分析:

  • $q0\to q0$: (b+ab)(ab)*(b+aa)
  • $q0\to f$: (b+ab)(ab)*(e+a)

消去 $q2$:

image-20210626155752836

答案:

$$ (aa+(b+ab)(ab)^*(b+aa))^*(a+(b+ab)(ab)^*(\varepsilon+a)) $$
(aa+(b+ab)(ab)*(b+aa))*(a+(b+ab)(ab)*($+a))