使用狀態消去法求給定有限自動機的正則表示式

問題

使用狀態消去法為給定的有限自動機生成正則表示式。

解決方案

將確定性有限自動機 (DFA) 轉換為正則表示式 (RE) 有兩種方法。

• Arden 定理方法。
• 狀態消去法。

給定的自動機如下所示：

步驟 1

初始狀態為 A，它有一條入邊。

因此，我們必須建立一個新的初始狀態 qi，如下所示：

步驟 2

初始狀態為 B，它有一條入邊。

因此，我們必須建立一個新的最終狀態 qf，如下所示：

步驟 3

現在，嘗試逐個消除所有中間狀態。

首先消除狀態 A

從狀態 qi 到 B 透過 A 有一條路徑。

因此，在消除狀態 A 後，我們可以連線從 qi 到 B 的直接路徑，其成本為。

ε.0=0

使用狀態 A 在狀態 B 上有一個迴圈。

因此，在消除狀態 A 後，我們可以繪製在狀態 B 上具有成本的直接迴圈。

1.0=10

**消除 A 後，我們得到以下結果：**

步驟 4

現在消除狀態 B

從狀態 qi 到 qf 透過狀態 B 有一條路徑。

因此，在消除 B 後，我們可以繪製從 qi 到狀態 qf 的直接路徑，其成本為

0.(10)* ε=0(10)*

最終正則表示式為 = 0(10)*

Bhanu Priya

更新於： 2021年6月11日

860 次檢視

開啟你的 職業生涯

完成課程獲得認證

開始學習