北邮形式语言与自动机四五章答案.doc

《北邮形式语言与自动机四五章答案.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、.形式语言与自动机作业参考答案（仅供参考）Ø第四章2．最左推导：E→E+T→T+T→E+T→b+T→b+T/F→b+F/F→b+b/F→b+b/b最右推导：E→E+T→E+T/F→E+T/b→E+F/b→E+b/b→T+b/b→F+b/b→b+b/b8.(1)由题：S,D,E为有用非终结符，删去有关C的生成式，得：G1:S→ED,D→a,E→b(2)由题：S,D,E为有用非终结符，删去有关C的生成式，得：G2:S→D,D→bS

2、b,E→DS

3、b.又E不可达，删去有关E得生成式，得：G2:S→D,D→bS

4、b9．由题：N

5、’={S,C,D,E},因为S∈N’，所以P1中加入生成式:S1→S

6、ε,变换后的无ε生成式的等价文法为：G1={N1,T,P1,S1}N1={S1,S,C,D,E}P1:S1→S

7、εS→DCE,D→CC,C→EE

8、b,E→DD

9、a10.把下列文法变换为无ε生成式、无单生成式和没有无用符号的等价文法：S→A1

10、A2,A1→A3

11、A4,A2→A4

12、A5,A3→S

13、b

14、ε,A4→S

15、a，A5→S

16、d

17、ε解:⑴由算法3，变换为无ε生成式：N’={S,A1,A2,A3,A4,A5}G1=({S1,S,A1,A2,A3,A4,A

18、5},{a,b,d},P1,S1),其中生成式P1如下：S1→ε

19、S,S→A1

20、A2,A1→A3

21、A4,A2→A4

22、A5,A3→S

23、b,A4→S

24、a,A5→S

25、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

26、b

27、d

28、ε,S→a

29、b

30、d,A1→a

31、b

32、d,A2→a

33、b

34、d,A3→a

35、b

36、d,A4→a

37、b

38、d,A5→a

39、b

40、d⑶由算法1和算法2，消除无用符号，得到符合题目要求

41、的等价文法：G1=({S1},{a,b,d},P1,S1)，其中生成式P1为：S1→a

42、b

43、d

44、ε.11.设2型文法G=({S,A,B,C,D,E,F},{a,b,c},P,S),其中P：S→ASB

45、ε;A→aAS

46、a;B→SBS

47、A

48、bb试将G变换为无ε生成式,无单生成式,没有无用符号的文法,再将其转换为..Chomsky范式.解:⑴由算法3，变换为无ε生成式：N’={S}由S→ASB得出S→ASB

49、AB,由A→aAS得出A→aAS

50、aA,由B→SBS得出B→SBS

51、SB

52、BS

53、B,由S∈N’得出S1→ε

54、S,因此无

55、ε的等效文法G1=({S1,S,A,B},{a,b,d},P1,S1),其中生成式P1如下：S1→ε

56、S,S→ASB

57、AB,A→aAS

58、aA

59、a,B→SBS

60、SB

61、BS

62、B

63、A

64、bb,⑵由算法4，消单生成式：NS1={S1,S},NS={S},NA={A},NB={A,B}由于S→ASB

65、AB∈P且不是单生成式,故P1中有S1→ε

66、ASB

67、AB,同理有S→ASB

68、AB,A→aAS

69、aA

70、a,B→SBS

71、SB

72、BS

73、aAS

74、aA

75、a

76、bb,因此生成的无单生成式等效文法为G1=({S1,S,A,B},{a,b},P1,S1

77、),其中生成式P1如下：S1→ε

78、ASB

79、AB,S→ASB

80、AB,A→aAS

81、aA

82、a,B→SBS

83、SB

84、BS

85、aAS

86、aA

87、a

88、bb,⑶由算法1和算法2，消除无用符号(此题没有无用符号);⑷转化为等价的Chomsky范式的文法:将S1→ASB变换为S1→AC,C→SB,将S→ASB变换为S→AC,将A→aAS

89、aA变换为A→ED

90、EA,D→AS,E→a,将B→SBS

91、aAS

92、aA

93、a

94、bb,变换为B→CS

95、ED

96、EA

97、FF,F→b,⑸由此得出符合题目要求的等价文法：G1=({S1,S,A,B,C,D},{a,b},P

98、1,S1),其中生成式P1如下：S1→ε

99、AC

100、AB,S→AC

101、AB,A→ED

102、EA

103、a,B→CS

104、SB

105、BS

106、ED

107、EA

108、a

109、FF,C→SB,D→AS,E→a,F→b.15.将下列文法变换为等价的Greibach范式文法:⑴S→DD

110、a,D→SS

111、b解:将非终结符排序为S,D,S为低位,D为高位,⑴对于D→SS,用S→DD

112、a代入得D→DDS

113、aS

114、b,..用引理4.2.4,变化为D→aS

115、b

116、aSD'

117、bD',D’→DS

118、DSD’,⑵将D生成式代入S生成式得S→aSD

119、bD

120、aSD’D

121、bD'D

122、a,⑶将D生成式代

123、入D’生成式得D’→aSS

124、bS

125、aSD'S

126、bD'S

127、aSSD'

128、bSD'

129、aSD'SD'

130、bD'SD',⑷由此得出等价的Greibach范式文法：G1=({S,D,D’},{a,b},P1,S),其中生成式P1如下：S→aSD

131、bD

132、aSD’D

133、bD'D

134、a,D→aS

135、b

136、aSD'

137、bD',D’→aSS

138、bS

139、aSD'S

140、bD