利用狀態消除方法生成有限狀態機的正則表示式

問題

給定一個有限狀態機，我們需要使用狀態消除方法將有限狀態機轉換成等效正則表示式。

第 1 步 - 初始狀態 q1 有傳入邊。因此，建立一個新的初始狀態 qi。

第 2 步 - 終止狀態 q2 有傳出邊。因此，建立一個新的終止狀態。

第 3 步 - 一個接一個地開始消除中間狀態。

  • 如果有路徑透過 q1 從 qi 進入 q2
  • 因此，消除 q1 之後，我們可以連線 qi 到 q2 的直接路徑，該路徑的成本為

    ε .c*.a=c*a

  • 使用狀態 qi 在 q2 上有一個迴圈
  • 因此，消除狀態 q1 之後，我們可以直接在狀態 q2 上繪製一個成本為

    b.c*.a=b.c*.a

第 4 步

現在消除 q2。

消除 q2 之後，從狀態 qi 到 qf 的直接路徑具有成本。

c*a(d+bc*a)* ε=c*a(d+bc*a)*

更新於： 2021 年 6 月 11 日

2K+ 瀏覽

開啟你的 職業生涯

完成課程獲得認證

開始學習
廣告