形式语言与自动机 四、五章部分习题答案
形式语言与自动机作业参考答案（仅供参考）
? 第四章
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,
1
形式语言与自动机 四、五章部分习题答案
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 ,
同理有 S →ASB | AB , A →aAS | aA | a , B →SBS | SB | BS | aAS | aA | a | bb, 因此生成的无单生成式等效文法为
G1 = ( { S1,S, A,B } , { a,b } , P1 , S1 ) ,其中生成式P1如下： S1 →ε| ASB | AB , S →ASB | AB , A →aAS | aA | a ,
B →SBS | SB | BS | aAS | aA | a | bb,
⑶ 由算法1和算法2，消除无用符号(此题没有无用符号); ⑷ 转化为等价的Chomsky范式的文法:
将S1 →ASB变换为 S →AC , C →SB ,
将S →ASB 变换为 S →AC ,
将A →aAS | aA 变换为 A →ED | EA, D →AS , E →a,
将B →SBS | aAS | aA | a | bb , 变换为 B →CS | ED | EA | FF, F →b , ⑸ 由此得出符合题目要求的等价文法：
G1 = ( { S1,S, A,B,C,D } , { a,b } , P1 , S1 ) ,其中生成式P1如下：
S1 →ε| AC | AB , S →AC | AB ,
A →ED | EA | a ,
B →CS | SB | BS | ED | EA | a | FF , C →SB , D →AS , E →a , F →b .
15. 将下列文法变换为等价的Greibach范式文法:
⑴ S →DD | a , D →SS | b
解: 将非终结符排序为S,D,S为低位,D为高位, ⑴ 对于D →SS ,用S →DD | a 代入得 D →DDS | aS | b ,
用引理4.2.4,变化为D →aS | b | aSD' | bD' , D’ →DS | DSD’ ,
⑵ 将D生成式代入S生成式得 S →aSD | bD | aSD’D | bD'D | a , ⑶ 将D生成式代入D’生成式得
D’ →aSS | bS | aSD'S | bD'S | aSS D' | bS D' | aSD'S D' | bD'S D' , ⑷ 由此得出等价的Greibach范式文法：
G1 = ( { S,D,D’ } , { a,b } , P1 , S ) ,其中生成式P1如下： S →aSD | bD | aSD’D | bD'D | a ,
D →aS | b | aSD' | bD' ,
D’ →aSS | bS | aSD'S | bD'S | aSS D' | bS D' | aSD'S D' | bD'S D' .
⑵ A1 →A3b | A2a , A2 →A1b | A2A2a | b , A3 →A1a | A3A3b | a 解: ⑴ 转化为等价的Chomsky范式的文法:
2
形式语言与自动机 四、五章部分习题答案
A1 →A3A4 | A2A5 , A2 A3 A4 A5
→A1A4 | A2A6 | b , →A1A5 | A3A7 | a , →b , →a ,
A6 →A2A5 , A7 →A3A4 ,
⑵ 转化为等价的Greibach范式的文法:
将非终结符排序为A1, A2,A3,A4,A5 ,A1为低位A5为高位,
①对于A2 →A1A4 ,用A1 →A3A4 | A2A5代入得A2 →A3A4A4 | A2 A5A4 | A2A6 | b , 用引理4.2.4,变化为
A2 →A3A4A4 | b | A3A4A4A2’ | bA2’ ,
A2’ →A5A4A2’ | A6A2’ | A5A4 | A6 ,
…… 此处隐藏2825字 ……
[q0,Z0,q0] →ε.
23. 证明下列语言不是上下文无关语言:
⑴ { anbncm | m≤n }; 证明:
假设L是上下文无关语言,由泵浦引理,取常数p,当ω∈L且|ω|≥p时,可取 ω = apbpcp ,将ω写为ω=ω1ω2ω0ω3ω4 ,同时满足|ω2ω0ω3|≤p
⑴ ω2和ω3不可能同时分别包含a和c,因为在这种情况下,有|ω2ω0ω3|>p;
5