Arden定理



為了找出有限自動機的正則表示式,我們使用Arden定理以及正則表示式的性質。

陳述

PQ為兩個正則表示式。

如果P不包含空串,則R = Q + RP 有唯一解R = QP*

證明

R = Q + (Q + RP)P [代入R = Q + RP]

= Q + QP + RPP

當我們反覆遞迴地代入R的值時,我們得到以下等式−

R = Q + QP + QP2 + QP3…..

R = Q (ε + P + P2 + P3 + …. )

R = QP* [因為P*表示(ε + P + P2 + P3 + ….)]

因此,得證。

應用Arden定理的假設

  • 狀態轉換圖不能有空轉移
  • 它必須只有一個初始狀態

方法

步驟1 − 為具有n個狀態和初始狀態q1的DFA的所有狀態建立如下形式的等式。

q1 = q1R11 + q2R21 + … + qnRn1 + ε

q2 = q1R12 + q2R22 + … + qnRn2

…………………………

…………………………

…………………………

…………………………

qn = q1R1n + q2R2n + … + qnRnn

Rij表示從qiqj的邊的標籤集,如果沒有這樣的邊,則Rij = ∅

步驟2 − 解這些方程以獲得最終狀態關於Rij的方程

問題

構造與下面給出的自動機對應的正則表示式−

Finite Automata

解答

這裡初始狀態和最終狀態是q1

三個狀態q1、q2和q3的方程如下:

q1 = q1a + q3a + ε (ε轉移是因為q1是初始狀態)

q2 = q1b + q2b + q3b

q3 = q2a

現在,我們將求解這三個方程:

q2 = q1b + q2b + q3b

= q1b + q2b + (q2a)b (代入q3的值)

= q1b + q2(b + ab)

= q1b (b + ab)* (應用Arden定理)

q1 = q1a + q3a + ε

= q1a + q2aa + ε (代入q3的值)

= q1a + q1b(b + ab*)aa + ε (代入q2的值)

= q1(a + b(b + ab)*aa) + ε

= ε (a+ b(b + ab)*aa)*

= (a + b(b + ab)*aa)*

因此,正則表示式是(a + b(b + ab)*aa)*。

問題

構造與下面給出的自動機對應的正則表示式−

Finite Automata1

解答

這裡初始狀態是q1,最終狀態是q2

現在我們寫下方程:

q1 = q10 + ε

q2 = q11 + q20

q3 = q21 + q30 + q31

現在,我們將求解這三個方程:

q1 = ε0* [因為,εR = R]

所以,q1 = 0*

q2 = 0*1 + q20

所以,q2 = 0*1(0)* [根據Arden定理]

因此,正則表示式是0*10*。

廣告