什麼是帶有 Epsilon 的 NFA 接受的語言？

由帶有 ε 的非確定有限自動機 (NFA) 接受的語言 L，表示為 M= (Q, Σ, 𝛿, q0, F)，可以定義如下：

設 M= (Q, Σ, 𝛿, q0, F) 為一個帶有 ε 的 NFA

其中，

• Q 是狀態集
• Σ 是輸入集
• δ 是從 Q x { Σ U ε } 到 2^Q 的轉移函式
• q0 是起始狀態
• F 是終結狀態

NFA 接受的字串 w 在 L 中可以表示如下：

L(M)={w| w ∈ Σ* 且 𝛿 從 q0 到 F 的 w 轉移}

示例

構造一個帶有 epsilon 的 NFA，它接受一個由任意數量的 a 後跟任意數量的 b 後跟任意數量的 c 組成的語言。

解決方案

這裡，任意數量的 a 或 b 或 c 意味著可以有零個或多個 a 後跟零個或多個 b 後跟零個或多個 c。

因此，帶有 epsilon 的 NFA 可以如下所示：

通常，epsilon 不顯示在輸入字串中。

帶有 epsilon 的 NFA 如下所示：

M = ({q0,q1,q2},{a,b}, 𝛿, q0,q2})

解釋

• 步驟 1 - q0 是初始狀態，q0 在 'a' 上轉到 q0 本身，在 epsilon 轉移上 q0 轉到 q1。
• 步驟 2 - q1 在 'b' 上轉到 q1 本身，在 epsilon 轉移上它轉到 q2。
• 步驟 3 - q2 在 'c' 上轉到 q2 本身，它是終結狀態。

轉移表如下所示：

考慮如下所示的字串 aabbcc：

δ(q0,aabbcc) |- δ(q0,abbcc)
             |- δ(q0,bbcc)
             |- δ(q0, εbbcc)
             |- δ(q1,bbcc)
             |- δ(q1,bcc)
             |- δ(q1,cc)
             |- δ(q1, εcc)
             |- δ(q2,cc)
             |- δ(q2,c)
             |- δ(q2, ε)

因此，在掃描完計算輸入字串後，我們到達了接受狀態。

Bhanu Priya

更新於：2021年6月12日

6K+ 瀏覽量

開啟您的 職業生涯

透過完成課程獲得認證

開始學習