構造正則語言 L = (00)*1(11)* 的 ∈-NFA

非確定有限自動機 (NFA) 中的 ε 轉移用於在沒有任何來自輸入集 Σ 的符號的情況下從一個狀態移動到另一個狀態。

ε-NFA 用五元組表示法定義

{Q, q0, Σ, δ, F}

其中，

  • δ − Q × (Σ∪ε)→2Q

  • Q − 有限狀態集

  • Σ − 有限輸入符號集

  • q0 − 初始狀態

  • F − 終結狀態

  • δ − 轉移函式

無 ε 轉移的 NFA

NFA 也具有與 DFA 相同的五個狀態，但具有不同的轉移函式，如下所示：

$$\delta\colon\:Q\times\:\sum\longrightarrow\:2^{Q}$$

其中，

  • Q：有限狀態集

  • Σ：有限輸入符號集

  • q0：初始狀態

  • F：終結狀態

  • δ：轉移函式

讓我們考慮給定的語言 L = (00)*1(11)*。

給定的語言分為三個部分 (00)*、1 和 (11)*。讓我們為每個部分構建狀態轉換圖，最後將這三個部分連線起來以獲得最終結果。

**步驟 1** - (00)* 的帶 epsilon 的 NFA 如下：

**步驟 2** - (11)* 的帶 epsilon 的 NFA 如下：

**步驟 3** - 將第一部分和第二部分與中間的 1 連線起來，如下所示：

更新於：2021年6月14日

2K+ 瀏覽量

開啟你的 職業生涯

完成課程獲得認證

開始學習
廣告