正则表达式转NFA，DFA，mDFA

RG :  (regular grammar)    正则文法

RE :  (regular expression)  正则表达式

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

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

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

RE转NFA、

举例：（a|b）*abb，拆分成(a|b)*和abb两个部分！！！

1）构造(a|b)*

a. 对于a构造如下NFA:

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

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

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

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

NFA转DFA、

根据图片所示NFA有0-10个状态，首先求出ε-closure(i)的集合，i是NFA状态编号。

• ε-closure(0) = {0,1,2,4,7};
• ε-closure(1) = {1,2,4};
• ε-closure(2) = {2};
• ε-closure(3) = {3,6,7,1,2,4};
• ε-closure(4) = {4};
• ε-closure(5) = {5,6,7,1,2,4};
• ε-closure(6) = {6,1,2,4,7};
• ε-closure(7) = {7};
• ε-closure(8) = {8};
• ε-closure(9) = {9};
• ε-closure(10) = {10};

• 初始编号开始为0,所以状态A = ε-closure(0) = {0,1,2,4,7}; move(A,a) = {3,8};
• NFA输入字母集合为{a,b}，所以计算ε-closure(move(A,a)) = ε-closure({3,8}) = ε-closure(3) ∪ ε-closure(8) = {1,2,3,4,6,7,8} = 状态B；
• move(A,b) = {5};计算ε-closure(move(A,b)) = ε-closure({5}) = {1,2,4,5,6,7} = 状态C ;
• move(B,a) = {3,8}; 计算ε-closure(move(B,a)) = ε-closure({3,8}) = {1,2,3,4,6,7,8} = 状态B;
• move(B,b) = {5,9};计算ε-closure(move(B,b)) = ε-closure({5,9}) = {1,2,4,5,6,7,9} = 状态D;
• move(C,a) = {3,8};计算ε-closure(move(C,a)) = ε-closure({3,8}) = {1,2,3,4,6,7,8} = 状态B;
• move(C,b) = {5};计算ε-closure(move(C,b)) = ε-closure({5}) = {1,2,4,5,6,7} = 状态C ;
• move(D,a) = {3,8};计算ε-closure(move(D,a)) = ε-closure({3,8}) = {1,2,3,4,6,7,8} = 状态B;
• move(D,b) = {5,10};计算ε-closure(move(D,b)) = ε-closure({5,10}) = {1,2,4,5,6,7,10} = 状态E;
• move(E,a) = {3,8};计算ε-closure(move(E,a)) = ε-closure({3,8}) = {1,2,3,4,6,7,8} = 状态B;
• move(E,b) = {5};计算计算ε-closure(move(E,b)) = ε-closure({5}) = {1,2,4,5,6,7} = 状态C ;
• 直到全部计算完成！！！

画出DFA转换表！！！DFA表有五种状态ABCDE,ε-closure(move(A,b))代表A行b列！！！

然后画图！！！