解释 TOC 中的 Arden 定理。
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+PP2
再次，用Q+RP替换R
=Q+QP+(Q+RP)P2
=Q+QP+QP2+RP3
因此，如果我们继续用Q+RP替换R，那么我们得到，
Q+RP=Q+QP+QP2+…………+QPi+RPi+1
=Q(ε+P+P2+…….+Pi)+RPi+1
从等式1
R=Q(ε+P+P2+…….+Pi)+RPi+1---------------方程2
其中i>=0
考虑等式2
R=Q(ε+P+P2+…….+Pi)+RPi+1
R=QP*+RPi+1
设w为长度为i的字符串
在RPi+1中没有小于i+1长度的字符串。
因此，
w不在集合RPi+1中
R和QP*代表同一个集合。
因此，证明
R=Q+RP有唯一解
R=QP*