细过程，并画出构造过程中的NFA、DFA的状态转换图，以及最小
DFA的状态转换图。答：（1）（３分）正规表达式：10100（2）（７分）第一步（３分）：将正规表达式转换为NFA
第二步（２分）：将NFA确定化为DFA：（１分）
状态输入
I0
I1
t
0
1
S

ADB
q0

q1
ADBDBC
DB
重新命名
q1
q2
q3
DBCDBCZDB
q2
q4
q3
DB
DBC
DBCZDBCZ
DFA的状态转换图（１分）
DBDB
q3
q2
q3
q4
q4
q3
第三步（２分）：将DFA最小化：（１分）
将状态划分终态与非终态两个集合：Ａ＝｛ｑ０，ｑ１，ｑ２，ｑ３｝，Ｅ＝｛ｑ４｝
根据Ａ、Ｅ集合的情况，对Ａ集合进行划分
状态输入
I0
I1
ｑ０

Ａ
ｑ１
Ａ
Ａ
ｑ２
Ｅ
Ａ
ｑ３
Ａ
Ａ
将状态集Ａ划分为两个集合：Ａ＝｛ｑ０，ｑ１，ｑ３｝，Ｂ＝｛２｝
根据Ａ、Ｂ集合的情况，对Ａ集合进行划分
状态输入
I0
I1
ｑ０

Ａ
ｑ１
Ｂ
Ａ
fｑ３
Ｂ
Ａ
将状态集Ａ划分为两个集合：Ａ＝｛ｑ０｝，Ｃ＝｛ｑ１，ｑ３｝
根据Ａ、Ｃ集合的情况，对Ｃ集合进行划分
状态输入
I0
I1
ｑ１
Ｂ
Ａ
ｑ３
Ｂ
Ａ
最小DFA的状态转换图（１分）
３．（20分）给定文法GE：E→ETTT→TFFF→Ei该文法是LL1文法吗？（要求给出详细过程，如果是LL（1），给出分析表）
答：（1）该文法不是LL（1）文法，因为有左递归，消除左递归可获得一个LL（1）文法（2）消除左递归，得新文法3分E→TE’E’→TE’εT→FT’T’→FT’εF→Ei3求产生式右部的First集25分FirstTE’FirstTFirstFiFirstTE’FirstFT’FirstFiFirstFT’FirstEFirstii
（4）求所有非终结符的Follow集25分FollowEFollowE’FollowEFollowTFirstE’∪FollowE∪FollowT’FollowTFollowFFirstT’∪FollowT∪FollowT’
（5）求所有产生式的Select集25分Select（E→TE’）FirstTE’iSelect（E’→TE’）FirstTE’Select（E’→ε）FollowE’Select（T→FT’）FirstFT’iSelect（T’→FT’）FirstFT’
（2分）
fSelect（T’→ε）FollowT’
Select（F→E）FirstE
Select（F→i）Firstii
（6）对相同左部的所有Select即求交集25分
Select（E’→TE’）∩Select（E’→ε）Φ
Select（T’→FT’）∩Select（T’→ε）Φ
Select（F→E）∩Select（F→i）Φ
所以，改造后的文法是LL（1）文法，其分析表如下
（7）LL1分析表（5分）
VN
r