如何將正則表示式轉換為有限自動機？

要將正則表示式 (RE) 轉換為有限自動機 (FA)，我們可以使用子集方法。

子集方法用於從給定的 RE 中獲取 FA。

• 步驟 1 − 使用帶 ε 移動的非確定性有限自動機 (NFA) 為給定的 RE 構造一個轉移圖。
• 步驟 2 − 將帶 ε 的 NFA 轉換為無 ε 的 NFA。
• 步驟 3 − 將 NFA 轉換為等價的確定性有限自動機 (DFA)。

一些基本的 RE 如下 −

情況 1 − 對於正則表示式“a”，我們可以構建如下所示的 FA −

情況 2 − 對於正則表示式“ab”，我們可以構建如下所示的 FA −

情況 3 − 對於正則表示式 (a+b)，我們可以構建以下 FA −

情況 4 − 對於 RE (a+b)*，我們可以構建如下所述的 FA −

班努·普里婭

更新於： 2021 年 6 月 12 日

18K+ 瀏覽量

啟動您的事業

完成課程以獲得認證

開始