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