阿登定理
为了找出有限自动机的正则表达式，我们使用阿登定理以及正则表达式的属性。
声明-
设P和Q为两个正则表达式。
如果P不包含空字符串，则R = Q + RP有唯一解，即R = QP*
证明-
R = Q + (Q + RP)P [输入值后R = Q + RP]
= Q + QP + RPP
当我们一次又一次递归地输入R的值时，我们得到以下等式 -
R = Q + QP + QP 2 + QP 3 ......
R = Q (ε + P + P 2 + P 3 + ….)
R = QP* [由于 P* 表示 (ε + P + P2 + P3 + ….) ]
于是，证明了。
应用雅顿定理的假设
- 转换图不得有 NULL 转换
- 它必须只有一个初始状态
方法
步骤 1 - 对于具有 n 个状态且初始状态为 q 1的 DFA 的所有状态，创建如下形式的方程。
q 1 = q 1 R 11 + q 2 R 21 + … + q n R n1 + ε
q 2 = q 1 R 12 + q 2 R 22 + … + q n R n2
…………………………
…………………………
…………………………
…………………………
q n = q 1 R 1n + q 2 R 2n + … + q n R nn
R ij表示从q i到q j 的边的标签集合，如果不存在这样的边，则R ij = ∅
步骤 2 - 求解这些方程以获得以R ij表示的最终状态方程
问题
构造与下面给出的自动机相对应的正则表达式 -
解决方案-
这里的初始状态和最终状态是q 1。
三个状态 q1、q2 和 q3 的方程如下 -
q 1 = q 1 a + q 3 a + ε (ε move 是因为 q1 是初始状态0
q 2 = q 1 b + q 2 b + q 3 b
q 3 = q 2 a
现在，我们将求解这三个方程 -
q 2 = q 1 b + q 2 b + q 3 b
= q 1 b + q 2 b + (q 2 a)b (q 3的代入值)
= q 1 b + q 2 (b + ab)
= q 1 b (b + ab)* （应用阿登定理）
q 1 = q 1 a + q 3 a + ε
= q 1 a + q 2 aa + ε (q 3的代入值)
= q 1 a + q 1 b(b + ab*)aa + ε (q 2的替换值)
= q 1 (a + b(b + ab)*aa) + ε
= ε (a+ b(b + ab)*aa)*
= (a + b(b + ab)*aa)*
因此，正则表达式为 (a + b(b + ab)*aa)*。
问题
构造与下面给出的自动机相对应的正则表达式 -
解决方案-
这里初始状态是 q 1，最终状态是 q 2
现在我们写下方程 -
q 1 = q 1 0 + ε
q 2 = q 1 1 + q 2 0
q 3 = q 2 1 + q 3 0 + q 3 1
现在，我们将求解这三个方程 -
q 1 = ε0* [As, εR = R]
所以，q 1 = 0*
q 2 = 0*1 + q 2 0
所以，q 2 = 0*1(0)* [根据雅顿定理]
因此，正则表达式为 0*10*。