个性化阅读
专注于IT技术分析

Arden定理

Arden定理对于检查两个正则表达式的等效性以及将DFA转换为正则表达式很有用。

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

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

1.令q1为初始状态。

2.有q2,q3,q4 …. qn个状态。最终状态可以是某个qj,其中j <= n。

3.令αji代表从qj到qi的过渡。

4.计算qi

qi =   αji  *   qj

如果qj是开始状态,则我们有:

qi = αji *  qj + ε

5.同样,计算最终给出正则表达式“ r”的最终状态。

例:

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

解:

让我们写下方程式

q1 = q1 0 + ε

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

同样,

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+)

赞(0) 打赏
未经允许不得转载:srcmini » Arden定理
分享到: 更多 (0)

评论 抢沙发

评论前必须登录!

 

觉得文章有用就打赏一下文章作者

微信扫一扫打赏