Arden 定理

为了找出有限自动机的正则表达式，我们使用 Arden 定理以及正则表达式的属性。

陈述 −

让 P 和 Q 成为两个正则表达式。

如果 P 不包含空字符串，则 R = Q + RP 有一个唯一解，即 R = QP*

证明 −

R = Q + (Q + RP)P [将值 R = Q + RP]

= Q + QP + RPP

当我们一次又一次地递归地输入R的值时，我们得到以下等式−

R = Q + QP + QP² + QP³…..

R = Q (ε + P + P² + P³ + …. )

R = QP* [正如P*所代表的(ε + P + P2 + P3 + ….) ]

因此，证明。

应用 Arden 定理的假设

• 转换图不得有 NULL 转换
• 它必须只有一个初始状态

方法

步骤 1 −为具有 n 个状态且初始状态为 q₁ 的 DFA 的所有状态创建以下形式的方程。

q₁ = q₁R₁₁ + q₂R₂₁ + … + q_nR_n1 + ε

q₂ = q₁R₁₂ + q₂R₂₂ + … + q_nR_n2

…………………………

…………………………

…………………………

…………………………

q_n = q₁R_1n + q₂R_2n + … + q_nR_nn

R_ij表示从q_i到q_j的边的标签集合，如果不存在这样的边，则R_ij = ∅

步骤2 −解这些方程，得到关于 R_ij

问题

构造一个与下面给出的自动机相对应的正则表达式 −

解决方案 −

此处的初始状态和最终状态为 q₁。

三个状态 q1、q2 和 q3 的方程如下 −

q₁ = q₁a + q₃a + ε (ε 移动是因为 q1 是初始状态 0

q₂ = q₁b + q₂b + q₃b

q₃ = q₂a

现在，我们将求解这三个方程式 −

q₂ = q₁b + q₂b + q₃b

= q₁b + q₂b + (q₂a)b (代入 q₃ 的值)

= q₁b + q₂(b + ab)

= q₁b (b + ab)* (应用 Arden 定理)

q₁ = q₁a + q₃a + ε

= q₁a + q₂aa + ε (代入 q₃ 的值)

= q₁a + q₁b(b + ab*)aa + ε (代入 q₂ 的值)

= q₁(a + b(b + ab)*aa) + ε

= ε (a+ b(b + ab)*aa)*

= (a + b(b + ab)*aa)*

因此，正则表达式为 (a + b(b + ab)*aa)*。

问题

构造与下面给出的自动机相对应的正则表达式 −

解决方案 −

此处初始状态为 q₁，最终状态为 q₂

现在我们写下方程式 −

q₁ = q₁0 + ε

q₂ = q₁1 + q₂0

q₃ = q₂1 + q₃0 + q₃1

现在，我们将求解这三个方程式 −

q₁ = ε0* [As, εR = R]

因此，q₁ = 0*

q₂ = 0*1 + q₂0

因此，q₂ = 0*1(0)* [根据 Arden 定理]

因此，正则表达式为 0*10*。