解释Arden定理在理论计算机科学中的应用。

Arden定理有助于检查两个正则表达式的等价性。

Arden定理

设P和Q是输入集Σ上的两个正则表达式。正则表达式R如下所示：

R=Q+RP

其唯一解为**R=QP*。**

证明

设P和Q是输入字符串集Σ上的两个正则表达式。

如果P不包含ε，则存在R使得

R= Q+RP-----------------------公式1

我们将用QP*替换公式1中的R

考虑公式1的右边(R.H.S)

= Q+QP*P

=Q(ε+P*P)

=QP* 因为根据恒等式R*R=R*

因此，R=QP* 得证。

为了证明R=QP*是唯一解，我们现在将公式1的左边(L.H.S)替换为Q+RP

然后它变成，Q+RP

但是，R可以再次被替换为Q+RP

因此，

Q+RP = Q+(Q+RP)P

=Q+QP+PP²

再次，用Q+RP替换R

=Q+QP+(Q+RP)P²

=Q+QP+QP²+RP³

因此，如果我们继续用Q+RP替换R，我们将得到：

Q+RP=Q+QP+QP²+………+QPⁱ+RPⁱ⁺¹

=Q(ε+P+P²+…….+Pⁱ)+RPⁱ⁺¹

从公式1

R = Q(ε+P+P²+…….+Pⁱ)+RPⁱ⁺¹ ---------------公式2

其中i>=0

考虑公式2

R= Q(ε+P+P²+…….+Pⁱ)+RPⁱ⁺¹

R= QP*+RPⁱ⁺¹

设w是一个长度为i的字符串

在RPⁱ⁺¹中没有长度小于i+1的字符串。

因此，

• w不在集合RPⁱ⁺¹中
• R和QP*表示相同的集合。

因此，已证明

R=Q+RP 有唯一解

R=QP*

Bhanu Priya

更新于：2021年6月12日

931 次浏览

启动你的职业生涯

完成课程获得认证

开始学习