编译原理：如何根据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.

可以以任意顺序终结状态，只留下从初态到终态，转换边上的表达式即为所求正则表达式。