资源描述：
《形式语言与自动机作业参考答案(仅供参考)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、形式语言与自动机四、五章部分习题答案形式语言与自动机作业参考答案（仅供参考）Ø第四章10.把下列文法变换为无ε生成式、无单生成式和没有无用符号的等价文法：S→A1
2、A2,A1→A3
3、A4,A2→A4
4、A5,A3→S
5、b
6、ε,A4→S
7、a，A5→S
8、d
9、ε解:⑴由算法3，变换为无ε生成式：N’={S,A1,A2,A3,A4,A5}G1=({S1,S,A1,A2,A3,A4,A5},{a,b,d},P1,S1),其中生成式P1如下：S1→ε
10、S,S→A1
11、A2,A1→A3
12、A4,A2→A4
13、A5,A3→S
14、b,A4→S
15、a,A5→S
16、d,
17、⑵由算法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
18、b
19、d
20、ε,S→a
21、b
22、d,A1→a
23、b
24、d,A2→a
25、b
26、d,A3→a
27、b
28、d,A4→a
29、b
30、d,A5→a
31、b
32、d⑶由算法1和算法2，消除无用符号，得到符合题目要求的等价文法：G1=({S1},{a,b,d},P1,S1)，其中生成式P1为：S1→a
33、b
34、d
35、ε.11.设2型文法G=({S,A,B,C,D,E,F},{a,b,c},P,S),
36、其中P：S→ASB
37、ε;A→aAS
38、a;B→SBS
39、A
40、bb试将G变换为无ε生成式,无单生成式,没有无用符号的文法,再将其转换为Chomsky范式.解:⑴由算法3，变换为无ε生成式：N’={S}由S→ASB得出S→ASB
41、AB,由A→aAS得出A→aAS
42、aA,由B→SBS得出B→SBS
43、SB
44、BS
45、B,由S∈N’得出S1→ε
46、S,因此无ε的等效文法G1=({S1,S,A,B},{a,b,d},P1,S1),其中生成式P1如下：S1→ε
47、S,S→ASB
48、AB,A→aAS
49、aA
50、a,8形式语言与自动机四、五章部分习题答案B→SBS
51、SB
52、
53、BS
54、B
55、A
56、bb,⑵由算法4，消单生成式：NS1={S1,S},NS={S},NA={A},NB={A,B}由于S→ASB
57、AB∈P且不是单生成式,故P1中有S1→ε
58、ASB
59、AB,同理有S→ASB
60、AB,A→aAS
61、aA
62、a,B→SBS
63、SB
64、BS
65、aAS
66、aA
67、a
68、bb,因此生成的无单生成式等效文法为G1=({S1,S,A,B},{a,b},P1,S1),其中生成式P1如下：S1→ε
69、ASB
70、AB,S→ASB
71、AB,A→aAS
72、aA
73、a,B→SBS
74、SB
75、BS
76、aAS
77、aA
78、a
79、bb,⑶由算法1和算法2，消除无用符号(此题没有
80、无用符号);⑷转化为等价的Chomsky范式的文法:将S1→ASB变换为S→AC,C→SB,将S→ASB变换为S→AC,将A→aAS
81、aA变换为A→ED
82、EA,D→AS,E→a,将B→SBS
83、aAS
84、aA
85、a
86、bb,变换为B→CS
87、ED
88、EA
89、FF,F→b,⑸由此得出符合题目要求的等价文法：G1=({S1,S,A,B,C,D},{a,b},P1,S1),其中生成式P1如下：S1→ε
90、AC
91、AB,S→AC
92、AB,A→ED
93、EA
94、a,B→CS
95、SB
96、BS
97、ED
98、EA
99、a
100、FF,C→SB,D→AS,E→a,F→b.15.将下列文法变换为等价
101、的Greibach范式文法:⑴S→DD
102、a,D→SS
103、b解:将非终结符排序为S,D,S为低位,D为高位,⑴对于D→SS,用S→DD
104、a代入得D→DDS
105、aS
106、b,用引理4.2.4,变化为D→aS
107、b
108、aSD'
109、bD',D’→DS
110、DSD’,⑵将D生成式代入S生成式得S→aSD
111、bD
112、aSD’D
113、bD'D
114、a,⑶将D生成式代入D’生成式得D’→aSS
115、bS
116、aSD'S
117、bD'S
118、aSSD'
119、bSD'
120、aSD'SD'
121、bD'SD',⑷由此得出等价的Greibach范式文法：G1=({S,D,D’},{a,b},P1,S),其中生成式P1如
122、下：S→aSD
123、bD
124、aSD’D
125、bD'D
126、a,D→aS
127、b
128、aSD'
129、bD',D’→aSS
130、bS
131、aSD'S
132、bD'S
133、aSSD'
134、bSD'
135、aSD'SD'
136、bD'SD'.⑵A1→A3b
137、A2a,A2→A1b
138、A2A2a
139、b,A3→A1a
140、A3A3b
141、a解:⑴转化为等价的Chomsky范式的文法:8形式语言与自动机四、五章部分习题答案A1→A3A4
142、A2A5,A2→A1A4
143、A2A6
144、b,A3→A1A5
145、A3A7
146、a,A4→b,A5→a,A6→A2A5,A7→A3A4,⑵转化为等价的Greibach范式的文法:将非终结符排序为A1,
147、A2,A3,A4,A5,A1为低位A5为高位,①对于A2→A1A4,用A1→A3A4
148、A2A5代入得A2→A3A4A4
149、A2A5A4
150、A2A6
151、b,用引理4.2.4,变化为A2→A3A4A4
152、b
153、A3A4A4A2’
154、bA
