解釋帶有 ε 轉移的 NFA。

我們透過允許瞬時 ε 轉移來擴充套件 NFA 的類別。

自動機可能允許在不讀取輸入符號的情況下更改其狀態。

在圖中，這種轉移透過用 ε 標記相應的弧來表示。

注意，這並不意味著 E 成為輸入符號。相反，我們假設符號 E 不屬於任何字母表。

  • ε-NFA 添加了一個方便的功能，但（從某種意義上說）它們並沒有給我們帶來任何新東西。它們並沒有擴充套件可以表示的語言的類別。
  • NFA 和 ε-NFA 都識別完全相同的語言。

Epsilon (ε) - 閉包

對於給定狀態 X，Epsilon 閉包是從狀態 X 出發，僅透過（空）或 ε 移動（包括狀態 X 本身）可以到達的狀態集。

換句話說，狀態的 ε-閉包可以透過遞迴地對從 X 出發透過單個 ε 移動可以到達的狀態的 ε-閉包進行並集運算來獲得。

示例

考慮以下帶有 ε 移動的 NFA 圖：

上述 NFA 的狀態轉移表如下：

狀態01epsilon
AB,CAB
B-BC
CCC-

對於上述示例，ε 閉包如下：

  • ε 閉包(A) : {A, B, C}
  • ε 閉包(B) : {B, C}
  • ε 閉包(C) : {C}

更新於：2021年6月12日

24K+ 次檢視

開啟你的職業生涯

完成課程獲得認證

開始學習
廣告