3、 已知正规式R=l(l|d)*，求最小DFA
分裂法子集法解：步骤：
1o 求NFA
l(l|d)*
x
2o 求DFA
子集法：构造确定化的矩阵
分割法R=>NFA=>DFA=>最小DFAl x l 1 ε 2 ε d y 分裂： y l A l B l d C d
3o 最小化DFA
分割法：首先将DFA分解成两个子集： π =({A},{B,C})
0分解{B,C}： 对l：
对d：
∴B,C等价：去掉C 最小化DFA：
l A l B d 非l 非d Z
注：实现时，扩充为：
l A l B d
且规定：字符串的长度为n,
4、 试写出在∑={a,b}上且不以a开头，但以aa结尾的字符串集合的正规式，并构造与之等价且状态最少的DFA。
根据状态矩阵得到状态图DFA M1 b 1
b 3 a b
a b a
b
0 2 4 a
最后，最小化。 先将状态分为非终结状态集{0,1,2,3}和终态集(4)。由状态矩阵（也可按最小化划分的方法求得）可知1和3状态在输入a或b所对应的下一个状态是对应相同的，故最后的划分为：{0},{1,3},{2},{4}。重新命名状态组{0}=0,{1,3}=1,{2}=2,{4}=3,则可得化简后的转换矩阵和最小化的DFA M: