答案：（1）首先为G中每个非终结符生成NFA的一个状态，开始符为初态，增加一新状态Z，做为NFA的终态。然后检查所有规则，对形如A→aB或A→B的产生式，构造M的转换函数f(A,a)=B或f(A,ε)=B；对形如A→a的产生式，构造M的转换函数f(A,a)=Z。故与G[S]等价的NFA如下图3-25所示。（2）用造表法将NFA确定化为DFA的步骤如下表3-11所示 ：新状态IaIbIcId1{S}{B}{A}ΦΦ2{B}Φ{E，Z}{B}{D}3{A}{C}{B}ΦΦ4{E，Z}Φ{E，Z}ΦΦ5{D}{C}ΦΦΦ6{C}Φ{F，Z }{B}{D}7{F，Z }Φ{E，Z}ΦΦ所得DFA如下图3-26所示。（3）用子集分割法将所得的DFA最小化过程：①根据是否为终态，划分DFA的状态集为：P0={{1，2，3，5，6}，{4，7}}。②根据各子集输出弧a、b、c、d所达到状态是否等价，最终划分为：P1={{1，3}，{5}，{2，6}，{4，7}}。③将P1的子集分别对应状态S、A、B、Z，得最小化后DFA如图3-27所示。（4）将最小化后的DFA转换为等价的正规式的过程如下。①将DFA的状态分为三部分：{S}，{A，B}，{Z}。分别求出这三部分对应的正规式为：R1=b*a，R2=(c｜da)*b，R3=b*。②将R1、R2和R3连接后得NFA对应的正规式为R=b*a(c｜da)*bb*。
