編譯原理：如何根據DFA生成正規表達式

編譯原理：如何根據語言/DFA生成正規表達式

• 前言
• • 兩種方法
• let us begin!
• • step 1
  • step2
  • step 3
  • step 4

前言

最近在複習編譯原理，遇到了給出語言，生成正規表達式的題目，發現呆坐法并不能成功解決類似題目，并發現大多此類問題都可以先根據語言畫出一個DFA，但是DFA如何轉正規表達式呢？

網上和書本上隻有正規表達式如何轉換成NFA，DFA的方法，周遊整個網絡，也沒有找到反向轉換的方法……

但是書本上說，DFA和正規表達式又是一一對應的。

是以！！一定存在某種方法！功夫不負有心人，終于讓筆者發現啦哈哈哈

兩種方法

有兩種比較流行的轉換方法，分别是：

1. Arden’s Method ，但是我沒有研究這個方法，我們研究第二種吧！
2. State Elimination Method，狀态終結法，終結它吧！！從此将語言轉換為正規表達式再也不用使用瞪眼找規律法了！

let us begin!

對于任何給出的DFA，我們隻需要經過以下幾步，就可以得到正規表達式！

step 1

The initial state of the DFA must not have any incoming edge.

DFA自動轉換機的初始狀态不可以有任何的入邊，如果有入邊，就要新産生一個初始狀态，以空指向原來的初始狀态！

step2

If there exists multiple final states in the DFA, then convert all the final states into non-final states and create a new single final state.

如果DFA有多個終态（接受态），那麼要把所有接受态以空邊指向新的接受态，使得DFA隻有一個接受态

step 3

If there exists any outgoing edge from the final state, then create a new final state having no outgoing edge from it.

DFA自動轉換機的終态如果有任何出邊，建立一個新的終态沒有出邊。

step 4

Eliminate all the intermediate states one by one.

These states may be eliminated in any order.

In the end,

• Only an initial state going to the final state will be left.
• The cost of this transition is the required regular expression.

可以以任意順序終結狀态，隻留下從初态到終态，轉換邊上的表達式即為所求正規表達式。