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

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

ID:15050867

大小:25.91 KB

页数:17页

时间:2018-08-01

北邮形式语言与自动机四五章答案_第1页
北邮形式语言与自动机四五章答案_第2页
北邮形式语言与自动机四五章答案_第3页
北邮形式语言与自动机四五章答案_第4页
北邮形式语言与自动机四五章答案_第5页
资源描述:

《北邮形式语言与自动机四五章答案》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库

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

5、9.由题:N’={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,A5},{a,b,d},P1,S1),其中

18、生成式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,消除无用符号,得到符合题目要求的等价文法:G1=({S1},{a,b,d},P1,S1),其中生成式P1为:S1→a

41、b

42、

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,变换为无ε生成式:1形式语言与自动机四、五章部分习题答案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,因此无ε的等效文法G1=({S1,S,A,B},{a,b,d},P1,S1),其中生成式P1如下:S1→ε

55、S,S→

56、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),其中生成式P1如下:S1→ε

77、ASB

78、AB,S→ASB

79、AB,A→aAS

80、aA

81、a,B→SBS

82、SB

83、BS

84、aAS

85、aA

86、a

87、bb,⑶由算法1和算法2,消除无

88、用符号(此题没有无用符号);⑷转化为等价的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},P1,S1),其中生成式P1如下:S1→ε

98、AC

99、AB,S→AC

100、AB,A→ED

101、EA

102、a,B→CS

103、SB

104、BS

105、ED

106、EA

107、a

108、FF,C→SB,D→AS,E→a,F→b.15.将下列文法变换为等价的Greibach

109、范式文法:⑴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生成式代入D’生成式得2形式语言与自动机四、五章部分习题答案⑷⑵解:⑴⑵D’→aSS

123、bS

124、aSD'S

125、bD'S

126、aSSD'

127、bSD'

128、aSD'SD'

129、bD'SD&#

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。