文库摘要：

单短语;T*F是相对于T的简单短语;
5.解:L(G[A])={bn-1a|n=1,2…}
L(G[W])={bn-1a2|n=1,2…}
证明:当n=1时,W Aa aa a2,显然结论成立;
假设n=k时W *bk-1a2;
则当n=k+1时,W Aa *bb k-1aa(bka2)
综上,结论对一切n>=1成立,即W *bn-1a2
在上面的规纳证明中,利用文法的一切规则且仅用了文法中的规则,因此,该文法产生的语言L(G[W])={ bn-1a2|n=1,2…}
6.(1)Z::=aAd|aZd
A::=bc|bAc
(2)Z::=AB
A::=ab|aAb
B::=b|Bb
7. 解:题中要求文法是:
Z::=1|3|5|7|9|Z1|Z3|Z5|Z7|Z9|A1|A3|A5|A7|A9
A::=2|4|6|8|A0|A2|A4|A6|A8|Z0|Z2|Z4|Z6|Z8
习题5
2. 最左推导:S (T) (T,S) (S,S) (a,S) (a,(T)) (a,(S)) (a,(b))
最右推导:S (T) (T,S) (T,(T)) (T,(S)) (T,(b)) (S,(b)) (a,(b))
最右推导是规范分析,最右推导每一步的句柄是:
①(;②T;③(;④S;⑤b;⑥S;⑦a
 

文库分享网（www.Wkfxw.com），全免费下载