解釋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 次瀏覽

啟動你的職業生涯

完成課程獲得認證

開始學習