第二章
习题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…} 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))
最右推导是规范分析,最右推导每一步的句柄是:
①(;②T;③(;④S;⑤b;⑥S;⑦a 4.(2)证明:
从上面两个语法树中可得出对于文法G[S]:S::=iScS|iS|i的句子iiici有两个不同的语法树 ,故得出该文法是二义性的. 5.(1)方法一:自顶向下
最右推导:
ZAAiBAiCAi(方法二:自底向上
Bi(
B+Ci(
B+(i(
C+(i(
(+(i(
最左归约: ZAAiB
AiCAi(Bi(B+Ci(B+(i(C+(i((+(i(
第三章
习题6
3.解：DFA D=（{A,B,C,D,E,F},{0,1},M,A,{E,F}） M： M(A,0)=B
M(B,0)=D M(B,1)=C M(C,0)=A M(C,1)=F M(D,0)=A M(D,1)=C M(E,0)=D M(E,1)=C M(F,0)=E M(F,1)=A
对于字符串0011011运行DFA D有： M(A,0011011)
=M(M(A,0),011011) =M(M(B,0),11011) =M(M(D,1),1011) =M(M(C,1),011) =M(M(F,0),11) =M(M(E,1),1) =M(C,1) =F
∴DFA D能接受字符串0011011 8.解：将状态转换图列表，即：
由左图可知，该状态转换图直接对应的是确定有穷状态自动机DFA DFA D=（{0,1,2,3,4,5},{a,b},M,0,{0,1}） M:M(0,a)=1 M(0,b)=2 M(1,a)=1 M(1,b)=4 M(2,a)=1 M(2,b)=3 M(3,a)=3 M(3,b)=2 M(4,a)=0 M(4,b)=5 M(5,a)=5 M(5,b)=1
化简： 1.分化
① {0,1} {2,3,4,5} ② {0,1} {2,4} {3,5} 2.合并
3.删除
没有无用状态和死状态，所以化简到此结束 状态最小化图：
9.(1)证明：e1|e2=e2|e1
|e1|e2|=|e1|∪|e2|=|e2|∪|e1|=|e2|e1| ∴e1|e2=e2|e1 (2)证明：(e1|e2)e3=e1e3|e2e3
|(e1|e2)e3|=|(e1|e2)||e3|=|e1|e2||e3|=(|e1|∪|e2|)|e3|=|e1||e3|∪|e2||e3|=|e1e3|∪|e2e3|=|e1e3|e2e3| ∴(e1|e2)e3=e1e3|e2e3
10．证明：e=b|ae当且仅当e={a}b 证：
充分性：正则表达式e=b|ae的值是这样一个正则集，以无数个小a开头，后跟一个小b。即：e={a}b。
必要性：|{a}b|=|{a}||b|=|a|*|b| ∴e=b|ae当且仅当e={a}b 11.(1)
从e构造转换系统：
去ε弧及无用状态和死状态：
由状态转换图构造NFA：
NFA A=({S,A,B,C,D,F,Z},{0,1},M,{S},{Z}) M:
由NFA产生DFA: