解释 TOC 中的 Arden 定理。

• Z时代
• 2024-01-10
• 分类：综合

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

阿登定理

设 P 和 Q 是输入集 Σ 上的两个正则表达式。正则表达式 R 给出如下 -

R=Q+RP

这有一个独特的解决方案，如R=QP*。

证明

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

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

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

我们将等式 1 中的 R 替换为 QP*

考虑等式 1 的右侧 (RHS)

= Q+QP*P

=Q(ε+P*P)

=QP* 因为 R*R=R* 根据身份

因此证明 R=QP*。

为了证明 R=QP* 是唯一解，我们现在将方程 1 的左侧 (LHS) 替换为 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+P2+…….+Pi)+RP ⁱ⁺¹ ---------------方程2

其中 i>=0

考虑等式 2

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

R= QP*+RP ⁱ⁺¹

设 w 为长度为 i 的字符串

在 RPi+1 中没有小于 i+1 长度的字符串。

因此，

• w 不在集合 RPi+1 中

• R 和 QP* 代表同一个集合。

因此，证明

R=Q+RP 有唯一解

R=QP*

以上是 解释 TOC 中的 Arden 定理。 的全部内容， 来源链接： utcz.com/z/331767.html