编译原理复习题(4)

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:

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库编译原理复习题(4)在线全文阅读。