資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究解釋 Arden 定理，用於將 DFA 轉換為正則表示式
將確定性有限自動機 (DFA) 轉換為正則表示式 (RE) 有兩種方法。這些方法如下所示：
- Arden 定理方法。
- 狀態消除方法。
讓我們詳細瞭解 Arden 定理方法。
Arden 定理
假設 P 和 Q 是兩個正則表示式。
如果 P 不包含空字串，則關於 R 的以下等式，即 R = Q + RP，
有一個唯一的解，即 R = QP*
這裡，
- 有限自動機 (FA) 沒有 ε 移動。
- 它必須只有一個初始狀態 q1。
- 它的狀態為 q1、q2、q3、…、qn。最終狀態可以是某個 qi，其中 i<=n。
- qi 是表示有限自動機接受的字串集的正則表示式，即使 qi 是最終狀態。
使用 Arden 定理查詢 DFA 的 RE。
為了找到給定自動機的正則表示式，我們可以首先為所有狀態建立給定形式的方程。
q1=q1α11+q2α21+----------+qnαn1+ε
q2=q1α12+q2α22+-----------+qnαn2
-
-
-
-
qn=q1α1n+q2α2n+------------+qnαnn。
透過重複應用替換和 Arden 定理，我們可以用 α ij 表示 qi。為了獲得有限狀態自動機 (FSA) 識別的字串集，我們必須取對應於最終狀態的所有 qi 的並集
示例
注意：對於並行邊，表示式中將存在該狀態的多個表示式。
然後，我們求解這些方程以獲得關於 α ij 的 qi 方程，並且該表示式是所需的解，其中 qi 是最終狀態。如下所示：
q 1= q a + 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) *。
5K+ 次檢視
