集
S
a
D
a，ε
T
b，d，ε
H
d，ε
FOLLOW集，b，d，e，b，d，eee
f由于predict（D→STe）∩predict（D→ε）a∩，b，d，e
predict（T→bH）∩predict（T→H）b∩epredict（H→d）∩predict（H→ε）d∩e所以该文法是LL1文法，LL1分析表如下表：
a
e
b
d

S
→aD
D
→STe
→ε
→ε
→ε
→ε
T
→H
→bH
→H
H
→ε
→d
6．判断下面文法是否为LL1文法，若是，请构造相应的LL1分析表。
S→aDD→STeε
T→bM
M→bHH→Mε答：文法的FIRST集和FOLLOW集
非终结符SD
FIRST集a
a，ε
FOLLOW集，b，b
T
b
e
M
b
e
H
b，ε
e
由于predict（D→STe）∩predict（D→ε）a∩，b
predict（H→M）∩predict（H→ε）b∩e
所以该文法是LL1文法，LL1分析表如下表：
a
e
b

fS
→aD
D
→STe
→ε
→ε
T
→bM
M
→bH
H
→ε
→M
7．某语言的拓广文法G′为：
0S′→S
1S→DbB
2D→dε
3B→Baε证明G不是LR0文法而是SLR1文法，请给出SLR1分析表。答：
拓广文法G，增加产生式S→S在项目集I0中：有移进项目D→d归约项目D→和B→存在移进归约和归约归约冲突，所以G不是LR0文法。
若产生式排序为：0S→S1S→Db2S→B3D→d4D→ε5B→Ba6B→εG′的LR0项目集族及识别活前缀的DFA如下图：
f由产生式知
FollowS
FollowDb
FollowBa在I0中FollowD∩db∩d
FollowB∩da∩d
FollowD∩FollowBb∩a在I3中FollowS∩a∩a所以在I0，I3中的移进归约和归约归约冲突可以由Follow集解决所以G是SLR1文法构造的SLR1分析表如下表：
状态
ACTION
b
d
a
GOTO

S
D
B
0
r4
S4
r6
r6
1
2
3
1
acc
2
S5
3
S6
r2
f4
r3
5
r1
6
r5
r5
8．给出与正规式R＝（ab）（ab）ba等价的NFA。答：与正规式R等价的NFA如下图
9．给出与正规式R＝（abb）（aba）a等价的NFA。答：与正规式R等价的NFA如下图
10．给出与正规式R＝（aba）（bab）b等价的NFA。答：与正规式R等价的NFA如下图
11．将下图的NFA确定化为DFA。
答：
f用子集法确定化如下表I
X121212312Y确定化后如下图：
Ia121212Y12
Ib123123123123
状态X123
12．将下图的NFA确定化为DFA。
答：用子集法确定化如下表
IX01301323Y
132YY确定化后如下图
Ia01301313
13
Ib23Y23Y
Y2YY
状态X1234Y
f13．某语言的拓广文法G′为：0S′→T1T→aBdε2B→Tbε
证明G不r