
- 自動機理論教程
- 自動機理論 - 首頁
- 自動機理論 - 入門
- 自動機理論 - 歷史
- 自動機理論 - 應用
- 自動機理論術語
- 自動機中字串的基礎知識
- 自動機的集合論
- 語言和文法
- 計算理論中的文法
- 由文法生成的語言
- 喬姆斯基文法分類
- 有限自動機
- 確定性有限自動機 (DFA)
- 非確定性有限自動機 (NFA)
- 從NFA到DFA的轉換
- DFA的最小化
- Moore機與Mealy機
- DFA的補集
- 正則表示式
- 自動機中的正則表示式
- 自動機中的Arden定理
- 將正則表示式轉換為有限自動機
- 正則文法的泵引理
- 計算理論中的正則集
- 上下文無關文法
- 上下文無關文法 (CFG)
- 上下文無關文法中的二義性
- 上下文無關語言的閉包性質
- 簡化上下文無關文法
- 喬姆斯基正規化 (CNF)
- 格雷巴赫正規化 (GNF)
- 上下文無關文法的泵引理
- 下推自動機
- 下推自動機 (PDA)
- 下推自動機的接受
- 從CFG構造PDA
- 下推自動機和語法分析
- 圖靈機
- 圖靈機 (TM) 基礎
- 圖靈機接受的語言
- 多磁帶圖靈機
- 多軌跡圖靈機
- 非確定性圖靈機
- 半無限帶圖靈機
- 線性界限自動機 (LBA)
- 可計算性和不可判定性
- 圖靈語言的可判定性
- 不可判定語言
- 圖靈機停機問題
- 計算理論中的Rice定理
- Post對應問題 (PCP)
- 自動機理論資源
- 自動機理論 - 快速指南
- 自動機理論 - 資源
- 自動機理論 - 討論
Arden定理
為了找出有限自動機的正則表示式,我們使用Arden定理以及正則表示式的性質。
陳述 −
設P和Q為兩個正則表示式。
如果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表示從qi到qj的邊的標籤集,如果沒有這樣的邊,則Rij = ∅
步驟2 − 解這些方程以獲得最終狀態關於Rij的方程
問題
構造與下面給出的自動機對應的正則表示式−

解答 −
這裡初始狀態和最終狀態是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)*。
問題
構造與下面給出的自動機對應的正則表示式−

解答 −
這裡初始狀態是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*。