資料結構
網路
關係型資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究如何將包含 ε 轉移的 NFA 轉換為不包含 ε 轉移的 NFA？
在這個方法中，我們嘗試從給定的非確定性有限自動機 (NFA) 中移除所有 ε 轉移。
該方法分步驟如下所述：
- 步驟 1 - 找出從 Q 中每個狀態出發的所有 ε 轉移。這將被稱為 ε-閉包(qi)，其中 qi ∈ Q。
- 步驟 2 - 然後，可以獲得 δ1 轉移。δ1 轉移表示對 δ 移動進行 ε-閉包。
- 步驟 3 - 對每個輸入符號和給定 NFA 的每個狀態重複步驟 2。
- 步驟 4 - 利用結果狀態，可以構建不含 ε 的等效 NFA 的狀態轉換表。
包含 ε 的 NFA 到不包含 ε 的 NFA 如下所示：
δ1(q,a) = ∈ - closure (δ (δ∈^(q,∈𝛜),a)) 其中，δ^(q,∈𝛜) = ∈ - closure(q)
示例
將給定的包含 ε 的 NFA 轉換為不包含 ε 的 NFA。
解決方案
我們首先獲得每個狀態的 ε-閉包，即找到從當前狀態 ε 可達的狀態。
因此，
- ε-closure(q0) = {q0,q1,q2}
- ε-closure(q1) = {q1,q2}
- ε-closure(q2) = {q2}
ε-closure(q0) 表示在空輸入（沒有輸入符號）的情況下，我們可以到達 q0、q1、q2。
類似地，可以獲得 q1 和 q2 的 ε-閉包。
現在，我們將獲得每個狀態在每個輸入符號上的 δ1 轉移，如下所示：
δ'(q0, 0) = ε-closure(δ(δ^(q0, ε),0))
= ε-closure(δ(ε-closure(q0),0))
= ε-closure(δ(q0,q1,q2), 0))
= ε-closure(δ(q0, 0) ∪ δ(q1, 0) U δ(q2, 0) )
= ε-closure(q0 U Φ ∪ Φ)
= ε-closure(q0)
= {q0,q1, q2}
δ'(q0, 1) = ε-closure(δ(δ^(q0, ε),1))
= ε-closure(δ(q0,q1,q2), 1))
= ε-closure(δ(q0, 1) ∪ δ(q1, 1) U δ(q2, 1) )
= ε-closure(Φ ∪q1 U Φ)
= ε-closure(q1)
= {q1, q2}
δ'(q0, 2) = ε-closure(δ(δ^(q0, ε),2))
= ε-closure(δ(q0,q1,q2), 2))
= ε-closure(δ(q0, 2) ∪ δ(q1, 2) U δ(q2, 2) )
= ε-closure(Φ U ΦU q2)
= ε-closure(q2)
= {q2}
δ'(q1, 0) = ε-closure(δ(δ^(q1, ε),0))
= ε-closure(δ(q1,q2), 0))
= ε-closure(δ(q1, 0) U δ(q2, 0) )
= ε-closure(Φ ∪ Φ)
= ε-closure(Φ)
= Φ
δ'(q1,1) = ε-closure(δ(δ^(q1, ε),1))
= ε-closure(δ(q1,q2), 1))
= ε-closure(δ(q1, 1) U δ(q2, 1) )
= ε-closure(q1 ∪ Φ)
= ε-closure(q1)
= {q1,q2}
δ'(q1, 2) = ε-closure(δ(δ^(q1, ε),2))
= ε-closure(δ(q1,q2), 2))
= ε-closure(δ(q1, 2) U δ(q2, 2) )
= ε-closure(Φ ∪ q2)
= ε-closure(q2)
= {q2}
δ'(q2, 0) = ε-closure(δ(δ^(q2, ε),0))
= ε-closure(δ(q2), 0))
= ε-closure(δ(q2, 0))
= ε-closure(Φ)
= Φ
δ'(q2, 1) = ε-closure(δ(δ^(q2, ε),1))
= ε-closure(δ(q2), 1)
= ε-closure(δ(q2, 1))
= ε-closure(Φ)
= Φ
δ'(q2, 2) = ε-closure(δ(δ^(q2, ε),))
= ε-closure(δ(q2), 2))
= ε-closure(δ(q2, 2))
= ε-closure(q2)
= {q2}現在，我們將總結所有計算出的 δ' 轉移，如下所示：
δ'(q0,0)={q0,q1,q2}
δ'(q0,1)={q1,q2}
δ'(q0,2)={q2}
δ'(q1,0)= { Φ }
δ'(q1,1)={q1,q2}
δ'(q1,2)={q2}
δ'(q2,0)={ Φ }
δ'(q2,1)={ Φ }
δ'(q2,2)={q2}狀態轉換表如下所示：
| 狀態\輸入 | 0 | 1 | 2 |
|---|---|---|---|
| q0 | {q0,q1,q2} | {q1,q2} | {q2} |
| q1 | Φ | {q1,q2} | {q2} |
| q2 | Φ | Φ | {q2} |
不包含 ε 的 NFA
不包含 ε 的 NFA 如下所示：
這裡，q0、q1、q2 是最終狀態，因為 ε-closure(q0)、ε-closure(q1) 和 ε-closure(q2) 包含最終狀態 q2。
更新於： 2021年6月12日
34K+ 瀏覽量
廣告