形式语言与自动机 四、五章部分习题答案 1 形式语言与自动机作业参考答案（仅供参考） 第四章 10. 把下列文法变换为无ε 生成式、无单生成式和没有无用符号的等价文法： S →A1 | A2 , A1 →A3 | A4 , A2 →A4 | A5 , A3 →S | b |ε , A4 →S | a，A5 →S | d |ε 解: ⑴ 由算法3，变换为无ε 生成式： N’ = { S, A1,A2,A3,A4,A5 } G1 = ( { S1,S, A1,A2,A3,A4,A5 } , { a,b,d } , P1 , S1 ) ,其中生成式P1 如下： S1 →ε | S , S →A1 | A2 , A1 →A3 | A4 , A2 →A4 | A5 , A3 →S | b , A4 →S | a , A5 →S | d , ⑵ 由算法4，消单生成式： NS1 = { S1,S,A1,A2,A3,A4, A5 } , NS = NA1 = NA2 = NA3 = NA4 = NA5 = { S, A1,A2,A3,A4, A5 } , 运用算法4，则 P1 变为： S1 →a | b | d |ε , S →a | b | d , A1 →a | b | d , A2 →a | b | d , A3 →a | b | d , A4 →a | b | d , A5 →a | b | d ⑶ 由算法1和算法2，消除无用符号，得到符合题目要求的等价文法： G1 = ( { S1 } , { a,b,d } , P1 , S1 ) ，其中生成式P1 为：S1 →a | b | d |ε . 11. 设 2 型文法G = ( { S,A,B,C,D,E,F } , { a,b,c } , P , S ) , 其中 P： S →ASB |ε ; A →aAS | a ; B →SBS | A | bb 试将 G 变换为无ε 生成式,无单生成式,没有无用符号的文法,再将其转换为Chomsky范式. 解: ⑴ 由算法3，变换为无ε 生成式： N’ = { S } 由 S →ASB 得出 S →ASB | AB , 由 A →aAS 得出 A →aAS | aA , 由 B →SBS 得出 B →SBS | SB | BS |B, 由 S∈N’ 得出 S1 →ε | S , 因此无ε 的等效文法G1 = ( { S1,S,A,B } , { a,b,d } , P1 , S1 ) ,其中生成式P1 如下： S1 →ε | S , S →ASB | AB , A →aAS | aA | a, 形式语言与自动机 四、五章部分习题答案 2 B →SBS | SB | BS | B| A | bb , ⑵ 由算法 4，消单生成式： NS1 = { S1,S } , NS = { S } , NA = { A } , NB = { A,B } 由于 S →ASB | AB∈P 且不是单生成式,故 P1 中有 S1 →ε | ASB | AB ,...
