什麼是非確定性有限自動機？

對於每個狀態，都存在與相應字母表中的每個符號相對應的精確一個轉移。這被稱為確定性有限自動機 (DFA)。

非確定性有限自動機 (NFA)

對於每個狀態，可以存在零個、一個、兩個或多個與特定符號相對應的轉移。

如果 NFA 進入一個狀態，該狀態存在多個與輸入符號相對應的可能的轉移，我們說它分支了。

如果 NFA 進入一個沒有有效轉移的狀態，則該分支終止。如果存在某個轉移選擇會導致最終進入接受狀態，則 NFA 接受輸入字串。

因此，一個接受分支足以使整體 NFA 接受，但所有分支都必須拒絕才能使整體 NFA 拒絕。

這是一個計算模型。我們編寫 DFA 來指定確定性有限自動機。正式地，NFA 是一個 5 元組 (Q, ∑, q0 , T, δ)，與之前一樣

  • Q 是有限的狀態集
  • ∑ 是輸入符號的字母表
  • q0 是起始狀態
  • T 是 Q 的子集，給出接受狀態
  • δ 是轉移函式。
  • 現在，轉移函式指定一組狀態而不是一個狀態：它將 Q☓ ∑ 對映到 {Q 的子集}。

示例 1

NFA 接受任何包含 00 或 11 作為子串的二進位制字串。如下所示：

示例 2

NFA 接受所有以 101 結尾的二進位制字串。如下所示：

更新於：2021年6月16日

1K+ 次瀏覽

開啟你的職業生涯

完成課程獲得認證

開始學習
廣告