
- 自動機理論教程
- 自動機理論 - 首頁
- 自動機理論 - 入門
- 自動機理論 - 歷史
- 自動機理論 - 應用
- 自動機理論術語
- 自動機中字串的基礎知識
- 自動機的集合論
- 語言和文法
- 計算理論中的文法
- 由文法生成的語言
- 喬姆斯基文法分類
- 有限自動機
- 確定性有限自動機 (DFA)
- 非確定性有限自動機 (NFA)
- 從 NFA 到 DFA 的轉換
- DFA 的最小化
- 穆爾機與米利機
- DFA 的補集
- 正則表示式
- 自動機中的正則表示式
- 自動機中的 Arden 定理
- 將正則表示式轉換為有限自動機
- 正則文法的泵引理
- 計算理論中的正則集
- 上下文無關文法
- 上下文無關文法 (CFG)
- 上下文無關文法中的二義性
- 上下文無關語言的封閉性
- 簡化上下文無關文法
- 喬姆斯基正規化 (CNF)
- 格雷巴赫正規化 (GNF)
- 上下文無關文法的泵引理
- 下推自動機
- 下推自動機 (PDA)
- 下推自動機的接受
- 由 CFG 構造 PDA
- 下推自動機和解析
- 圖靈機
- 圖靈機 (TM) 基礎
- 圖靈機接受的語言
- 多磁帶圖靈機
- 多軌跡圖靈機
- 非確定性圖靈機
- 半無限帶圖靈機
- 線性界自動機 (LBA)
- 可計算性和不可判定性
- 圖靈語言的可判定性
- 不可判定語言
- 圖靈機停機問題
- 計算理論中的 Rice 定理
- Post 對應問題 (PCP)
- 自動機理論資源
- 自動機理論 - 快速指南
- 自動機理論 - 資源
- 自動機理論 - 討論
非確定有限自動機
在 NDFA 中,對於特定的輸入符號,機器可以移動到機器中任何狀態的組合。換句話說,無法確定機器移動到的確切狀態。因此,它被稱為非確定自動機。因為它具有有限數量的狀態,所以該機器被稱為非確定有限機或非確定有限自動機。
NDFA 的形式化定義
NDFA 可以用 5 元組 (Q, ∑, δ, q0, F) 表示,其中 -
Q 是一個有限的狀態集。
∑ 是一個有限的符號集,稱為字母表。
δ 是轉移函式,其中 δ: Q × ∑ → 2Q
(這裡取 Q 的冪集 (2Q),因為在 NDFA 的情況下,從一個狀態可以發生到 Q 狀態的任何組合的轉移)
q0 是處理任何輸入的初始狀態 (q0 ∈ Q)。
F 是 Q 的最終狀態集 (F ⊆ Q)。
NDFA 的圖形表示:(與 DFA 相同)
NDFA 用稱為狀態圖的有向圖表示。
- 頂點表示狀態。
- 用輸入字母標記的弧表示轉移。
- 初始狀態用空單個傳入弧表示。
- 最終狀態用雙圓圈表示。
示例
令一個非確定性有限自動機為 →
- Q = {a, b, c}
- ∑ = {0, 1}
- q0 = {a}
- F = {c}
轉移函式 δ 如下所示 -
當前狀態 | 輸入 0 的下一個狀態 | 輸入 1 的下一個狀態 |
---|---|---|
a | a, b | b |
b | c | a, c |
c | b, c | c |
它的圖形表示如下所示 -

DFA 與 NDFA
下表列出了 DFA 和 NDFA 之間的區別。
DFA | NDFA |
---|---|
從一個狀態的轉移對於每個輸入符號都是到單個特定下一個狀態。因此,它被稱為確定性。 | 從一個狀態的轉移對於每個輸入符號可以是到多個下一個狀態。因此,它被稱為非確定性。 |
DFA 中沒有看到空字串轉移。 | NDFA 允許空字串轉移。 |
DFA 允許回溯 | 在 NDFA 中,回溯並不總是可能的。 |
需要更多空間。 | 需要更少空間。 |
如果一個字串轉移到最終狀態,則 DFA 接受該字串。 | 如果所有可能的轉移中至少有一個以最終狀態結束,則 NDFA 接受一個字串。 |
接受器、分類器和變換器
接受器(識別器)
計算布林函式的自動機稱為接受器。接受器的所有狀態要麼接受要麼拒絕給它的輸入。
分類器
分類器具有兩個以上的最終狀態,並且在終止時給出單個輸出。
變換器
根據當前輸入和/或先前狀態產生輸出的自動機稱為變換器。變換器可以分為兩種型別 -
米利機 - 輸出取決於當前狀態和當前輸入。
穆爾機 - 輸出僅取決於當前狀態。
DFA 和 NDFA 的可接受性
當且僅當 DFA/NDFA 從初始狀態開始,在完全讀取字串後結束於接受狀態(任何最終狀態)時,DFA/NDFA 接受一個字串。
如果 DFA/NDFA (Q, ∑, δ, q0, F) 接受字串 S,則
δ*(q0, S) ∈ F
DFA/NDFA 接受的語言L 是
{S | S ∈ ∑* 且 δ*(q0, S) ∈ F}
如果 DFA/NDFA (Q, ∑, δ, q0, F) 不接受字串 S′,則
δ*(q0, S′) ∉ F
DFA/NDFA 不接受的語言 L′(接受語言 L 的補集)是
{S | S ∈ ∑* 且 δ*(q0, S) ∉ F}
示例
讓我們考慮圖 1.3 中所示的 DFA。從 DFA 中,可以匯出可接受的字串。

上述 DFA 接受的字串:{0, 00, 11, 010, 101, ...........}
上述 DFA 不接受的字串:{1, 011, 111, ........}