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

形式语言与自动机四、五章部分习题答案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,形式语言与自动机四、五章部分习题答案2B→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|aSSD'|bSD'|aSD'SD'|bD'SD',⑷由此得出等价的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|aSSD'|bSD'|aSD'SD'|bD'SD'.⑵A1→A3b|A2a,A2→A1b|A2A2a|b,A3→A1a|A3A3b|a解:⑴转化为等价的Chomsky范式的文法:形式语言与自动机四、五章部分习题答案3A1→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|A2A5A4|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→A3A4A5|A3A4A4A5A5|bA5A5|A3A4A4A2’A5A5|bA2’A5A5|A3A7|a,用引理4.2.4,变化为A3→bA5A5|bA2’A5A5|a|bA5A5A3’|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|bA5,④对于A7→A3A4,将A3生成式代入A7生成式得A7→bA5A5A4|bA2’A5A5A4|aA4|bA5A5A3’A4|bA2’A5A5A3’A4|aA3’A4,⑤将A5,A6生成式代入A2’生成式得A2’→aA4A2’|bA5A5A4A4A5A2’|bA2’A5A5A4A4A5A2’|aA4A4A5A2’|bA5A5A3’A4A4A5A2’|bA2’A5A5A3’A4A4A5A2’|aA3’A4A4A5A2’|bA5A5A4A4A2’A5A2’|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|bA5,将A4,A7生成式代入A3’生成式得A3’→aA5|aA4A5A5|aA4A2’A5A5|aA5A3’|aA4A5A5A3’|aA4A2’A5A5A3’|bA5A5A4|bA2’A5A5A4|aA4|bA5A5A3’A4|bA2’A5A5A3’A4|aA3’A4|bA5A5A4A3’|bA2’A5A5A4A3’|aA4A3’|bA5A5A3’A4A3’|bA2’A5A5A3’A4A3’|aA3’A4A3’,⑶由此得出等价的Greibach范式文法:G1=({S,D,D’},{a,b},P1,S),其中生成式P1如下：A1→A3A4|A2A5,形式语言与自动机四、五章部分习题答案4A2→A3A4A4|b|A3A4A4A2’|bA2’,A3→bA5A5|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|bA5,A7→bA5A5A4|bA2’A5A5A4|aA4|bA5A5A3’A4|bA2’A5A5A3’A4|aA3’A4,A2’→aA4A2’|bA5A5A4A4A5A2’|bA2’A5A5A4A4A5A2’|aA4A4A5A2’|bA5A5A3’A4A4A5A2’|bA2’A5A5A3’A4A4A5A2’|aA3’A4A4A5A2’|bA5A5A4A4A2’A5A2’|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|bA5,A3’→aA5|aA4A5A5|aA4A2’A5A5|aA5A3’|aA4A5A5A3’|aA4A2’A5A5A3’|bA5A5A4|bA2’A5A5A4|aA4|bA5A5A3’A4|bA2’A5A5A3’A4|aA3’A4|bA5A5A4A3’|bA2’A5A5A4A3’|aA4A3’|bA5A5A3’A4A3’|bA2’A5A5A3’A4A3’|aA3’A4A3’.20.设文法G有如下得生成式:S→aDD,D→aS|bS|a,构造等价的下推自动机.解:根据P162-163的算法,构造下推自动机M,使M按文法G的最左推导方式工作.设M=(Q,T,Г,δ,q0,Z0,F),其中Q={q0,qf},T={a,b},Г={a,b,D,S},Z0=S,F={qf},δ定义如下:δ(q0,ε,S)={(q0,aDD)},δ(q0,ε,D)={(q0,aS),(q0,bS),(q0,a)},δ(q0,a,a)={(q0,ε)},δ(q0,ε,ε)={(qf,ε)}.21.给出产生语言L={aibjck|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|ε文法具有二义性。因为当句子ω中a,b,c个数相同时，对于ω存在两个不同的最左(右)推导。如abcL，存在两个不同的最左推导SADaAbDabDabcCabc及SEBaEBaBabBcabc。22.设下推自动机M=({q0,q1},{a,b},{Z0,X},δ,q0,Z0,φ),其中δ如下:形式语言与自动机四、五章部分习题答案5δ(q0,b,Z0)={(q0,XZ0)},δ(q0,ε,Z0)={(q0,ε)},Aδ(q0,b,X)={(q0,XX)},δ(q1,b,X)={(