本文格式为Word版，下载可任意编辑第4章词法分析作业参考答案 第4章词法分析作业参考答案 4.7练习（P72） 1．构造以下正规式相应的DFA： (4) b((ab)*|bb)*ab 解：先将正规式转换为NFA，转换过程如下： 以下为最终所得的NFA图： 然后，将此NFA转换为DFA： 转换关系矩阵如下表： C T0={1} T1={2,4} T2={5,6} T3={3} T4={2,4,7} 所得DFA图如下： Ta Φ T2={5,6} Φ Φ T2={5,6} Tb T1={2,4} T3={3} T4={2,4,7} T1={2,4} T3={3} 结果，将此DFA化简后如下： 4、把图4.21（a）和（b）分别确定化和最小化： (a)图【解】子集法： { 0} {0,1} {1} 重命名： Ia {0,1} {0,1} {0} Ib {1} {1} - 0 1 2 Ia 1 1 0 Ib 2 2 ￠ 确定化的DFA为： (b)图【解】 【解】 初始划分得Π0：终态组{0}，非终态组{1,2,3,4,5} 对非终态组举行分割： {1,2,3,4,5}a ={0,1,3,5} 而{0,1,3,5}既不属于{0}，也不属于{1,2,3,4,5} ∵{4} a {0}，所以得新划分 Π1：{0}，{4}，{1,2,3,5} 对{1,2,3,5}举行分割： ∵{1,5} b {4} {2,3} b {1,2,3,5}，故得新划分 Π2：{0}，{4}，{1, 5}，{2,3} {1, 5} a {1, 5} {2,3} a {1,3}，故状态2和状态3不等价，得新划分： Π3：{0}，{2}，{3}，{4}，{1, 5}这是结果划分 最小DFA： 7．给文法G[S]： S→aA|bQ A→aA|bB|b B→bD|aQ Q→aQ|bD|b D→bB|aA E→aB|bF F→bD|aE|b 构造相应的最小的DFA。
【解】首先，将正规式转换成NFA如下： 然后，将此NFA转换为DFA： 转换关系矩阵如下表： C T0={S} T1={A} T2={Q} T3={Z,B} T4={Z.D} T5={D } T6={B} 所得DFA图如下： Ta T1={A} T1={A} T2={Q} T2={Q} T1={A} T1={A} T2={Q} Tb T2={Q} T3={Z,B} T4={Z.D} T5={D } T6={B} T6={B} T5={D } 化简后的结果划分为：T0={T0},T1={T1,T2},T3={T3,T4},T5={T5,T6},其中T3为终态 结果，将此DFA化简后如下： — 3 —。