前言： 正则语言等价描述模型的转换

图1 正则语言等价描述模型转换

RG :  (regular grammar)    正则文法

RE :  (regular expression)  正则表达式

DFA :  (deterministic finite automaton)  确定的有穷状态自动机

NFA :  (non-deterministic finite automaton)  不确定的有穷状态自动机

ε-NFA : (non-deterministic finite automaton with ε-moves) 带空移动的不确定有穷状态自动机

RE转DFA

举例：（a|b）*abb

1. RE转NFA

拆分成(a|b)*和abb两个部分

1）构造(a|b)*

a. 对于a构造如下NFA:

图2 a的NFA

b. 对于b的构造如下NFA:

图3

c. a|b的NFA如图4所示

图4

d. (a|b)*的NFA如图5所示

图5

2） 构造abb，连接在图5所示NFA后面即可,最终结果如图6所示

图6

2. NFA转DFA

1) NFA状态集上的操作

图7

2） 图6中NFA转DFA

a) 开始状态A是ε-closure(0),即A={0,1,2,4,7}。

注意：状态0也是可以从自身出发经过ε到达的状态

b) NFA输入字母表为{a,b}

先计算状态A经过a所得到的集合B--ε-closure(move(A,a))

move(A,a)={3,8}

ε-closure（{3,8})）={1,2,3,4,6,7,8}

同理，计算状态A经过b得到的集合C:ε-closure(move(A,b)) =ε-closure({5})={1,2,3,6,7}

之后对集合B,C继续这个处理过程，最终使得这个DFA的所有状态都被加上标记,结果如图8所示

图8

构造DFA结果如图9所示

图9

3. DFA最小化

1) 初始分组

     分为非接受状态组和接受状态组

       {A,B,C,D}和{E}

2) 分割

    因为组{E}只包含一个状态，不能再被分割了

    另一个{A,B,C,D}

            考虑输入a的时候，这些状态都转向B，因此使用以a开头的串无法区分这些状态

            考虑输入b的时候，A,B,C转到组{A,B,C,D}的某个成员上，而D转向另一个组的成员E   上，因此将{A,B,C,D}分割成{A,B,C}和{D},得到新一轮状态组{A,B,C}{D}{E}

3) 再次分割

     考虑组{A,B,C}

           输入b时，A,C到达{A,B,C}中的元素，B到达另一个组中的元素D,因此分割后的状态组为{A,C}{B}{D}{E}

4) 分割完成

     {A,C}无法再进行分割，所以最终的状态组就为{A,C}{B}{D}{E}

5) 最小DFA

从状态组中挑选出A,B,D,E作为对应组的代表，其转换函数如图10所示

图10

最终的DFA如图11所示

图11

参考

形式语言与自动机理论

编译原理（紫龙书）