非確定有限自動機



在 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

它的圖形表示如下所示 -

NDFA Graphical Representation

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 中,可以匯出可接受的字串。

Acceptability of String by DFA

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

上述 DFA 不接受的字串:{1, 011, 111, ........}

廣告