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 *。
【Arden定理】假设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+)
推荐阅读
- 自动机上下文无关语法(CFG)
- RE到FA的自动机转换
- 自动机正则表达式的例子
- 自动机正则表达式
- 从NFA到DFA的自动机转换
- 自动机从ε NFA到DFA的转换
- 消除ε转换的自动机
- 非确定性有限自动机的例子
- 非确定性有限自动机(NFA)