第二章
习题1
6.答:省略表示法:{1.3,1.33,1.333…};描述表示法:{1.3i|i=1,2,3…}
7.答:x+={0,12,123,1234…};
x*={,0,12,123…}
8.答:长度为0的符号串个数:0个
长度为1的符号串个数:26个
长度为2的符号串个数:26*36=936个
长度为3的符号串个数:26*36*36=33696个
长度不大于3的符号串个数:26+936+33696=34658个
有代表性的符号串:a,a0,aa,a00,a0a,aa0
习题2
3.(1)ETT/FF/F(E)/F(E+T)/F(T+T)/F(F+F)/F(i+i)/i
(2)EE+TE+T+TE+T*F+FE+T*F+iE+T*T*F+i
E+T*F*F+i E+T*F*i+i
短语:E+T是相对于E的短语;F是相对于T的短语;i是相对于F的短语;T*F是相对于T的短语;E+T+T是相对于E的短语;E+T+F是相对于E的短语;E+T+i是相对于E的短语;
E+T*F是相对于E的短语;E+T*F*F是相对于E的短语;E+T*F*i是相对于E的短语;
E+T*F*i+i是相对于E的短语.
简单短语:E+T是相对于E的简单短语;F是相对于T的简单短语;i是相对于F的简单短语;T*F是相对于T的简单短语;
5.解:L(G[A])={bn-1a|n=1,2…}
字符串长度算不算 0
L(G[W])={bn-1a2|n=1,2…}
证明:当n=1时,WAaaaa2,显然结论成立;
假设n=k时W*bk-1a2;
则当n=k+1时,WAa*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))

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。