將正則表示式 1(0+1)*0 轉換為等效 DFA。

若要將正則表示式轉換成有限狀態自動機（FA），我們可以使用子集方法。

使用子集方法可以從給定的正則表示式（RE）中獲得 FA。

  • 步驟 1 − 使用帶 ε 移動的非確定性有限狀態自動機 (NFA) 為給定的 RE 構建轉移圖。
  • 步驟 2 − 將帶 ε 的 NFA 轉換為不帶 ε 的 NFA。
  • 步驟 3 − 將 NFA 轉換為等效 DFA。

我們將給定的表示式分成以下三部分 −

“1” 、 “（0+1)*” 和 “0”

帶有 Epsilon 轉移的 NFA 如下 −

現在，我們將刪除 Epsilon 轉移。

刪除後，轉移圖如下所示 −

更新於： 2021 年 6 月 12 日

5K+ 檢視

開啟您的 職業

透過完成課程獲得認證

開始
廣告