形式语言与自动机作业参考答案(仅供参考)

形式语言与自动机作业参考答案（仅供参考）第四章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，消单生成式：N S1 = { S1,S,A1,A2,A3,A4, A5 } ,N S = N A1 = N A2 = N A3 = N A4 = N A5 = { 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,B →SBS | SB | BS | B| A | bb ,⑵由算法4，消单生成式：N S1 = { S1,S } , N S = { S } , N A = { A } , N B = { 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范式的文法:A1→A3A4 | A2A5 ,A2→A1A4 | A2A6 | b ,A3→A1A5 | A3A7 | a ,A4→b ,A5→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 ,②对于A3→A1A5 ,用A1→A3A4 | A2A5代入得A3→A3A4A5 | A2A5A5 | A3A7 | a ,A3生成式右边第一个字符仍是较低位的非终结符,将A2生成式代入A3生成式得A3→A3A4 A5 | A3A4A4 A5A5 | b A5A5 | A3A4A4A2’ A5A5 | bA2’A5A5 | A3A7 | a ,用引理4.2.4,变化为A3→b A5A5 | bA2’A5A5 | a | b A5A5A3’ | bA2’A5A5A3’ | aA3’ ,A3’→A4A5| A4A4A5A5| A4A4A2’A5A5| A7| A4A5A3’| A4A4A5A5A3’| A4A4A2’A5A5A3’ | A7A3’ ,③对于A6→A2A5 ,将A2生成式代入A6生成式得A6→A3A4A4A5 | bA5 | A3A4A4A2’A5 | bA2’A5 ,A6生成式右边第一个字符仍是较低位的非终结符,将A3生成式代入A6生成式得A6→bA5A5A4A4A5| bA2’A5A5A4A4A5| aA4A4A5| bA5A5A3’A4A4A5| bA2’A5A5A3’A4A4A5| aA3’A4A4A5| bA5A5A4A4A2’A5| bA2’A5A5A4A4A2’A5| aA4A4A2’A5| bA5A5A3’A4A4A2’A5| bA2’A5A5A3’A4A4A2’A5| aA3’A4A4A2’A5| bA2’A5 | b A5 ,④对于A7→A3A4 , 将A3生成式代入A7生成式得A7→b A5A5A4 | bA2’A5A5A4 | a A4 | b A5A5A3’A4 | bA2’A5A5A3’A4 | aA3’A4 ,⑤将A5,A6生成式代入A2’生成式得A2’→aA4A2’| bA5A5A4A4A5A2’| bA2’A5A5A4A4A5A2’| aA4A4A5A2’| bA5A5A3’A4A4A5A2’ | bA2’A5A5A3’A4A4A5A2’ | aA3’A4A4A5A2’ | bA5A5A4A4A2’A5 A2’| bA2’A5A5A4A4A2’A5A2’| aA4A4A2’A5A2’| bA5A5A3’A4A4A2’A5A2’| bA2’A5A5A3’A4A4A2’A5A2’| aA3’A4A4A2’A5A2’| bA2’A5A2’| b A5A2’| aA4| b A5A5A4A4A5 | bA2’A5A5A4A4A5 | aA4A4A5 | bA5A5A3’A4A4A5 | bA2’A5A5A3’A4A4A5 | aA3’A4A4A5| bA5A5A4A4A2’A5| bA2’A5A5A4A4A2’A5| aA4A4A2’A5| bA5A5A3’A4A4A2’A5 | bA2’A5A5A3’A4A4A2’A5 | aA3’A4A4A2’A5 | bA2’A5 | b A5 ,将A4,A7生成式代入A3’生成式得A3’→aA5 | aA4A5A5 | aA4A2’A5A5 | aA5A3’ | aA4A5A5A3’ | aA4A2’A5A5A3’ | b A5A5A4 | bA2’A5A5A4| aA4| bA5A5A3’A4| bA2’A5A5A3’A4| aA3’A4| bA5A5A4A3’| bA2’A5A5A4A3’ | a A4A3’ | b A5A5A3’A4 A3’ | bA2’A5A5A3’A4 A3’ | aA3’A4A3’ ,⑶由此得出等价的Greibach范式文法:G1 = ( { S,D,D’ } , { a,b } , P1 , S ) ,其中生成式P1如下：A1→A3A4 | A2A5 ,A2→A3A4A4 | b | A3A4A4A2’ | bA2’ ,A3→b A5A5 | bA2’A5A5 | a | bA5A5A3’ | bA2’A5A5A3’ | aA3’ ,A4→b ,A5→a ,A6→bA5A5A4A4A5| bA2’A5A5A4A4A5| aA4A4A5| bA5A5A3’A4A4A5|bA2’A5A5A3’A4A4A5| aA3’A4A4A5| bA5A5A4A4A2’A5| bA2’A5A5A4A4A2’A5|aA4A4A2’A5| bA5A5A3’A4A4A2’A5| bA2’A5A5A3’A4A4A2’A5| aA3’A4A4A2’A5|bA2’A5 | b A5 ,A7→b A5A5A4 | bA2’A5A5A4 | a A4 | b A5A5A3’A4 | bA2’A5A5A3’A4 | aA3’A4 ,A2’→aA4A2’| bA5A5A4A4A5A2’| bA2’A5A5A4A4A5A2’| aA4A4A5A2’|bA5A5A3’A4A4A5A2’ | bA2’A5A5A3’A4A4A5A2’ | aA3’A4A4A5A2’ | bA5A5A4A4A2’A5 A2’| bA2’A5A5A4A4A2’A5A2’| aA4A4A2’A5A2’| bA5A5A3’A4A4A2’A5A2’|bA2’A5A5A3’A4A4A2’A5A2’| aA3’A4A4A2’A5A2’| bA2’A5A2’| bA5A2’| aA4| bA5A5A4A4A5 | bA2’A5A5A4A4A5 | aA4A4A5 | bA5A5A3’A4A4A5 | bA2’A5A5A3’A4A4A5 |aA3’A4A4A5| bA5A5A4A4A2’A5| bA2’A5A5A4A4A2’A5| aA4A4A2’A5|bA5A5A3’A4A4A2’A5 | bA2’A5A5A3’A4A4A2’A5 | aA3’A4A4A2’A5 | bA2’A5 | b A5 ,A3’→aA5 | aA4A5A5 | aA4A2’A5A5 | aA5A3’ | aA4A5A5A3’ | aA4A2’A5A5A3’ | b A5A5A4 |bA2’A5A5A4| aA4| bA5A5A3’A4| bA2’A5A5A3’A4| aA3’A4| bA5A5A4A3’|bA2’A5A5A4A3’ | a A4 A3’ | b A5A5A3’A4 A3’ | bA2’A5A5A3’A4 A3’ | aA3’A4A3’ .20.设文法G有如下得生成式: S →aDD , D →aS | bS | a , 构造等价的下推自动机.解: 根据P162-163的算法,构造下推自动机M,使M按文法G的最左推导方式工作.设M = (Q,T,Г,δ,q0,Z0,F ),其中Q = { q0,q f } ,T = { a,b} ,Г= { a,b,D,S } ,Z0 = S ,F = { q f } ,δ定义如下:δ( q0,ε,S) = { ( q0, aDD ) } ,δ( q0,ε,D ) = { ( q0,aS ) , ( q0,bS ) , ( q0,a ) } ,δ( q0,a,a ) = { ( q0,ε) } ,δ( q0,ε,ε) = { ( q f,ε) } .21.给出产生语言L = { a i b j c k | i , j , k≥0 且i = j 或者j = k }的上下文无关文法.你给出的文法是否具有二义性?为什么?解: G=({S,A,B,C,D,E},{a,b,c}，P，S)P：S →AD |EB, A→aAb |ε, B →bBc |ε, D →cD |ε, E →aE |ε文法具有二义性。