從正則表示式構造有限自動機

---

---

我們可以使用湯姆遜構造法從正則表示式中找出有限自動機。我們將把正則表示式簡化為最小的正則表示式，並將這些表示式轉換為NFA，最後轉換為DFA。

一些基本的RA表示式如下：

情況1 - 對於正則表示式“a”，我們可以構造以下FA：

情況2 - 對於正則表示式“ab”，我們可以構造以下FA：

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

情況4 - 對於正則表示式(a+b)*，我們可以構造以下FA：

方法

步驟1 從給定的正則表示式構造一個帶有空移動的NFA。

步驟2 去除NFA中的空轉移，並將其轉換為等價的DFA。

問題

將以下RA轉換為等價的DFA：1(0+1)*0

解決方案

我們將連線三個表示式“1”、“(0+1)*”和“0”。

現在我們將移除ε轉移。在從NDFA中移除ε轉移後，我們得到以下結果：

這是一個對應於RE - 1(0+1)*0的NDFA。如果要將其轉換為DFA，只需應用第1章中討論的將NDFA轉換為DFA的方法。

帶有空移動的有限自動機 (NFA-ε)

帶有空移動的有限自動機 (FA-ε) 不僅在從字母集接收輸入後轉換，而且在沒有任何輸入符號的情況下轉換。這種無需輸入的轉換稱為空移動。

NFA-ε 由一個 5 元組 (Q, ∑, δ, q₀, F) 形式表示，包括

• Q - 一個有限的狀態集

• ∑ - 一個有限的輸入符號集

• δ - 一個轉移函式 δ : Q × (∑ ∪ {ε}) → 2^Q

• q₀ - 一個初始狀態 q₀ ∈ Q

• F - Q 的一組最終狀態/狀態 (F⊆Q)。

上述(FA-ε) 接受一個字串集 - {0, 1, 01}

從有限自動機中移除空移動

如果在一個NDFA中，頂點X到頂點Y之間存在ϵ-移動，我們可以使用以下步驟將其移除：

• 查詢從Y發出的所有邊。
• 複製從X開始的所有這些邊，而不更改邊標籤。
• 如果X是初始狀態，則使Y也成為初始狀態。
• 如果Y是最終狀態，則使X也成為最終狀態。

問題

將以下NFA-ε 轉換為沒有空移動的NFA。

解決方案

步驟1 -

這裡 ε 轉移在q₁和q₂之間，所以設q₁為X，q_f為Y。

這裡從q_f發出的邊是對於輸入0和1到q_f。

步驟2 -

現在我們將複製從q₁開始的所有這些邊，而不更改從q_f開始的邊，並獲得以下FA：

步驟3 -

這裡q₁是初始狀態，所以我們也使q_f成為初始狀態。

所以FA變為：

步驟4 -

這裡q_f是最終狀態，所以我們也使q₁成為最終狀態。

所以FA變為：