看看實際效果
NFA 圖表範例。
同一款工具，四種需求。下方每張圖都是實際產生的成果。
輸入內容
繪製一個以 a 和 b 為字母、只接受以 ab 結尾字串的 NFA：q0 對 a 和 b 形成迴圈，q0 可在讀取 a 時移動到 q1，而 q1 在讀取 b 時移動到接受狀態 q2。
接著試試為被拒絕的已完成輸入新增一個陷阱狀態。將目標後綴從 ab 改成 ba。
狀態圖 · OMG UML 2.5.1 §14 + Harel (1987) statechart · schematex-state
產生的圖表
什麼是 NFA 圖表。
NFA 圖表是非確定有限自動機的狀態圖。圓圈代表狀態，箭頭代表轉移，指向狀態的箭頭代表起始狀態，雙圓圈代表接受狀態。
與 DFA 不同，NFA 可在讀取相同輸入符號時採取多個轉移，也可使用不消耗輸入的 ε 轉移。只要至少有一條可能的路徑在接受狀態結束，字串就會被接受。
- Standard
- OMG UML 2.5.1 §14 + Harel (1987) statechart
- Engine
- schematex-state
- Editable
- Double-click text, drag nodes
- Export
- SVG · PNG · PDF
適用對象
誰會使用 NFA 圖表。
用於正規語言練習，展示機器如何辨識後綴、前綴或子字串。
用於繪製小型 ε-NFA，讓課堂筆記中的正規運算式聯集更容易理解。
在轉換成實作前，將替代的 token 前綴繪製成分支。
運作方式
三個步驟建立 NFA 圖表。
01
描述需求
寫一段話就能開始。
“繪製一個以 a 和 b 為字母、只接受以 ab 結尾字串的 NFA：q0 對 a 和 b 形成迴圈，q0 可在讀取 a 時移動到 q1，而 q1 在讀取 b 時移動到接受狀態 q2。”
02
查看圖表
由合適的繪圖引擎產生。
03
提出修改
每次修改都會保留版本。
為被拒絕的已完成輸入新增一個陷阱狀態。
V2 · DRAWN FROM V1, NOTHING RETYPED常見問題
常見問題
什麼是 NFA？
非確定有限自動機是一種有限狀態機，對同一個輸入符號可能有多個轉移。只要至少有一條通過機器的路徑在接受狀態結束，它就會接受該輸入。
NFA 和 DFA 有什麼不同？
DFA 對每個狀態和輸入符號各有一個下一個狀態。NFA 可以分支到多個狀態，也可以包含 ε 轉移，但 NFA 和 DFA 能辨識相同類別的正規語言。
什麼是 ε 轉移？
ε 轉移可以在不消耗輸入字元的情況下變更狀態。從正規運算式建立 NFA 時，通常會用它來連接或分割分支。
接受狀態如何表示？
接受狀態或終止狀態會以雙圓圈表示。只有在讀完所有輸入後，某條路徑以該狀態結束時，機器才會接受輸入。
可以從正規運算式建立 NFA 嗎？
可以。描述運算式和字母表，再說明想在狀態圖中明確呈現的群組或交替。
相關工具
