Automata Theory 简明教程
Arden’s Theorem
为了找出有限自动机的正则表达式,我们使用 Arden 定理以及正则表达式的性质。
Statement -
设 P 和 Q 是两个正则表达式。
如果 P 不包含 null 字符串,则 R = Q + RP 具有唯一解 R = QP *
Proof −
R = Q + (Q + RP)P [在代入了 R = Q + RP 之后]
Q + QP + RPP
当我们不断递归地代入 R 的值时,我们得到以下方程 -
R = Q + QP + QP2 + QP3…..
R = Q (ε + P + P2 + P3 + …. )
R = QP* [因为 P* 表示 (ε + P + P2 + P3 + ….) ]
因此得证。
Assumptions for Applying Arden’s Theorem
-
转换图不得包含 NULL 转换
-
它只能有一个初始状态
Method
Step 1 - 对于所有具有 n 个状态的 DFA 状态(初始状态为 q1),创建以下形式的方程。
q1 = q1R11 + q2R21 + … + qnRn1 + ε
q2 = q1R12 + q2R22 + … + qnRn2
…………………………
…………………………
…………………………
…………………………
qn = q1R1n + q2R2n + … + qnRnn
Rij 表示从 qi 到 qj 的边的标签集合,如果不存在这样的边,则 Rij = ∅
Step 2 — 求解这些方程式,以 Rij 的形式获得最终状态方程式
Problem
构造与以下给定自动机相对应的正则表达式 −
Solution −
此处初始状态和最终状态为 q1 。
三个状态 q1、q2 和 q3 的方程式如下 −
q1 = q1a + q3a + ε(ε 移动是因为 q1 是初始状态 0
q2 = q1b + q2b + q3b
q3 = q2a
现在,我们将求解这三个方程式 −
q2 = q1b + q2b + q3b
q1b + q2b + (q2a)b (Substituting value of q3)
q1b + q2(b + ab)
q1b (b + ab)* (Applying Arden’s Theorem)
q1 = q1a + q3a + ε
q1a + q2aa + ε (Substituting value of q3)
q1a + q1b(b + ab*)aa + ε (Substituting value of q2)
q1(a + b(b + ab)*aa) + ε
ε (a+ b(b + ab)aa)
(a + b(b + ab)aa)
因此,正则表达式为 (a + b(b + ab) aa) 。
Problem
构造与以下给定自动机相对应的正则表达式 −
Solution −
此处初始状态为 q1,最终状态为 q2
现在我们写下方程式 −
q1 = q10 + ε
q2 = q11 + q20
q3 = q21 + q30 + q31
现在,我们将求解这三个方程式 −
q1 = ε0* [,εR = R]
所以,q1 = 0*
q2 = 0*1 + q20
所以,q2 = 0*1(0)* [由艾登定理]
因此,正则表达式为 0*10*。