长度不大于3的符号串个数:26+936+33696=34658个
有代表性的符号串:a,a0,aa,a00,a0a,aa0
习题2
3.(1)E T T/F F/F (E)/F (E+T)/F (T+T)/F (F+F)/F (i+i)/i
(2)E E+T E+T+T E+T*F+F E+T*F+i E+T*T*F+i
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.合并
=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}）
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))
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)
16 #E′T′)E i+i)/i# E∷=TE′
17 #E′T′) E′T i+i)/i# T∷=FT′
18 #E′T′) E′T′′ i+i)/i#
20 #E′T′) E′T′ +i)/i# T′∷=ε
21 #E′T′) E′ +i)/i# E′∷=+E
8 #E′T′ i-(i+i)/i#
9 #E′T′ -(i+i)/i# T′∷=ε
10 #E′ -(i+i)/i# E′∷=-E
11 #E- -(i+i)/i#
12 #E (i+i)/i# E∷=TE′
13 #E′T (i+i)/i# T∷=FT′
14 #E′T′F (i+i)/i# F∷=(E)
15 #E′T′)E( (i+i)/i#
(2)Bell有向图法 （非形式化）
步骤一、构造有向图
步骤二、对各结点所能达到的结点个数计数，最终可列表：
步骤三、检查可得f与g的值与原有的优先矩阵一致，所以上表函数即为所求优先函数
R∷=deQ′caR′|bQ′caR′|daR′|deQ′fR′|bQ′fR′|ε
Step3: G′[S]:
S∷=Qc|Rd|c
Q∷=RdeQ′|ceQ′|RbQ′|bQ′
Q′∷=ceQ′|ε
R∷=ceQ′caR′|bQ′caR′|caR′|ceQ′fR′|bQ′fR′|aR′
R∷=deQ′caR′|bQ′caR′|daR′|deQ′fR′|bQ′fR′|ε
Q∷=RdeQ′|ceQ′|RbQ′|bQ′
Q′∷=ceQ′|ε
i=3,j=1:U3=R∷=Qca|Rda|ca|Qf|a
j=2:R∷=RdeQ′ca|ceQ′ca|RbQ′ca|bQ′ca|Rda|ca|RdeQ′f|cf|
RbQ′f|bQ′f|a
消去规则左递归：
R∷=ceQ′caR′|bQ′caR′|caR′|ceQ′fR′|bQ′fR′|aR′
∴(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构造转换系统：
5.(1)方法一:自顶向下
最右推导:
Z A AiB AiC Ai( Bi( B+Ci( B+(i( C+(i( (+(i(
方法二:自底向上
最左归约:
Z A AiB AiC Ai( Bi( B+Ci( B+(i( C+(i( (+(i(
第三章
习题6
3.解：DFA D=（{A,B,C,D,E,F},{0,1},M,A,{E,F}）
由于最终归约到了识别符号Z,识别出符号串b(aa)b.是文法G5.2的句子.
所构造的推导是:
Z=>bMb=>b(Lb=>b(Ma)b=>b(aa)b
习题9
3.试为下列优先矩阵构造优先函数
(1)逐次加一法构造优先函数:
步骤一、置初始值
步骤二、关于优先关系 修改f与g的值成
步骤三、关于优先关系±修改f与g的值成，而此时构造过程已收敛，即优先函数值与优先关系完全一致，则该优先矩阵所对应的优先函数为：
第二章
习题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个
follow(E)={#,)}
follow(E′)={#,)}
follow(T)={#,),+,-}
follow(T′)={#,),+,-}
follow(F)={*,/,#,),+,-}
识别输入符号串i*i-(i+i)/i,则识别过程
步骤 栈 输入 输出
0 #E i*i-(i+i)/i# E∷=TE′
22 #E′T′)E+ +i)/i#
23 #E′T′)E i)/i# E∷=TE′
24 #E′T′) E′T i)/i# T∷=FT′
25 #E′T′) E′T′F i)/i#
26 #E′T′) E′T′ i)/i#
27 #E′T′) E′T′ )/i# T′∷=ε
28 #E′T′) E′ )/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时,W Aa aa a2,显然结论成立;
去ε弧及无用状态和死状态：
由状态转换图构造NFA：
NFA A=({S,A,B,C,D,F,Z},{0,1},M,{S},{Z})
M:
由NFA产生DFA:
分化:①{[S],[C],[A],[AD],[AF],[ABF]} {[AFZ]}
②{[S]} {[C]} {[A],[AF],[ABF]} {[AD]} {[AFZ]}
把②代入③得，V=(Va+c)b+c
=Vab+cb+c
把它改写成V=(cb+c){ab},因此V=(cb|c){ab} ⑤
把④⑤代入①得，W=Ua+Vb=(ca|c){ba}a+(cb|c){ab}b
因此 W=(ca|c){ba}a|(cb|c){ab}b
第四章
6、试消去文法G[S]：
S∷=Qc|Rd|c
Q∷=Rb|Se|b
R∷=Sa|Qf|a
文法左递归与规则左递归。
解： step1:U1=S U2=Q U3=R
step2:i=1,j=1: j>i-1,不执行关于j的循环，且关于U1=S不存在规则左递归
i=2,j=1: U2=Q∷=(Qc|Rd|c)e|Rb|b
=Qce|Rde|ce|Rb|b
消去规则左递归：
此文法没有多余规则，所以消去左递归后的文法就是G′[S]
4、试为文法G[P]：
P∷=begin S end S∷=A|C
A∷=V:=E C∷=if E then S
E∷=V E∷=E+V V∷=i
采用某种程序设计语言构造递归下降识别程序。
解：由于文法存在左递归，进行文法等价变换，得到等价文法G′[P]：
29 #E′T′) )/i#
30 #E′T′ /i# T′∷=/T
31 #E′T/ /i#
32 #E′T i# T∷=FT′
33 #E′T′F i#
34 #E′T′ i#
35 #E′T′ # T′∷=ε
36 #E′ # E′∷=ε
37 # #