Arden 定理

阿登定理可用于检查两个正则表达式的等价性，以及将DFA转换为正则表达式。

让我们看看它在将DFA转换为正则表达式中的应用。

使用以下算法从给定的DFA构建正则表达式形式。

1. 设 q₁ 为初始状态。

2. 有 q₂, q₃, q₄ ....q_n 个状态。 最终状态可以是某个 q_j，其中 j<= n。

3. 设 α_ji 表示从 q_j 到 q_i 的转换。

4. 计算 q_i 使得

   qi =   αji  *   qj

如果 q_j 是开始状态，那么我们有

   qi = αji *  qj + ε

5. 同样，计算最终状态，最终给出正则表达式 'r'。

示例

为给定的DFA构建正则表达式

解决方案

让我们写下这些方程

q1 = q1 0 + ε 

由于 q1 是开始状态，因此将添加 ε，并且输入 0 从 q1 到 q1，因此我们写
状态 = 输入的源状态 × 到它的输入

类似地，

q2 = q1 1 + q2 1
q3 = q2 0 + q3 (0+1)

由于最终状态是 q1 和 q2，我们只对求解 q1 和 q2 感兴趣。 让我们先看看 q1

q1 =  q1 0 + ε

我们可以将其重写为

q1 = ε + q1 0

这类似于 R = Q + RP，并简化为 R = OP*。

假设 R = q1, Q = ε, P = 0

我们得到

q1 = ε.(0)*
q1 = 0*    (ε.R*= R*)

将值代入 q2，我们将得到

q2 = 0* 1 + q2 1
q2 = 0* 1 (1)*   (R = Q + RP  →  Q P*)

正则表达式由以下给出

r = q1 + q2
= 0* + 0* 1.1*
r = 0* + 0* 1+    (1.1* = 1+)