确定化：
重新命名，令AB为B、AC为C、ABY为D得：
所以，可得DFA为：
23. 文法 S->a|^|(T) T->T,S|S
对 (a,(a,a) 和 (((a,a),^,(a)),a) 的最左推导。 解： 对(a,(a,a)的最左推导为： S=>(T) =>(T,S) =>(S,S) =>(a,S) =>(a,(T)) =>(a,(T,S)) =>(a,(S,S)) =>(a,(a,S)) =>(a,(a,a))
对(((a,a),^,(a)),a) 的最左推导为： S=>(T) =>(T,S) =>(S,S) =>((T),S)
=>((T,S),S) =>((T,S,S),S) =>((S,S,S),S)
=>(((T),S,S),S) =>(((T,S),S,S),S) =>(((S,S),S,S),S) =>(((a,S),S,S),S) =>(((a,a),S,S),S) =>(((a,a),^,S),S) =>(((a,a),^,(T)),S) =>(((a,a),^,(S)),S) =>(((a,a),^,(a)),S) =>(((a,a),^,(a)),a) 24. 文法： S->MH|a H->LSo| ε K->dML| ε L->eHf M->K|bLM
判断 G 是否为 LL(1) 文法，如果是，构造 LL(1) 分析表。 解：各符号的FIRST集和FOLLOW集为：
11
预测分析表为：
由于预测分析表中无多重入口，所以可判定文法是LL(1)的。 25．叙述由下列正规式描述的语言 (a)0(0|1)*0 (b)((ε|0)1*)* (c)(0|1)*0(0|1)(0|1) (d)0*10*10*10*
(e)(00|11)*((01|10)(00|11)*(01|10)(00|11)*)*
解：(a)以0开头、以0结尾的所有0和1的串。 (b)由0和1组成的串，包括空串。
(c)倒数第3个字符为0，由0和1组成的串。 (d)含有3个1的所有0和1的串。
(e)由偶数个0和偶数个1构成的所有0和1的串。
26．已知文法G[S]： S→(L)|a L→L,S|S
为句子(a,(a,a))构造最左推导和最右推导。 解：句子(a,(a,a))的最左推导为：
S=>(L)=>(L,S) =>(S,S)=>(a,S) =>(a,(L))=>(a,(L,S)) =(a,(S,S))=>(a,(a,S))=>(a,(a,a))
句子(a,(a,a))的最右推导为：
S=>(L)=>(L,S) =>(l,(L))=>(L,(L,S))=>(L,(L,a))=>(L,(S,a))=>(L,(a,a))=(S,(a,a))=(a,(a,a))
五.计算题
1．构造下述文法 G[S] 的自动机： S->A0
A->A0|S1|0
该自动机是确定的吗？若不确定，则对它确定化。
解：由于该文法的产生式S->A0，A->A0|S1中没有字符集VT的输入，所以不是确定的自动机。 要将其他确定化，必须先用代入法得到它对应的正规式。把S?A0代入产生式A?S1有：A=A0|A01|0=A(0|01)|0=0(0|01)*。 代入S->A0有该文法的正规式：0(0|01)*0，所以，改写该文法为确定的自动机为：
12
由于状态A有3次输入0的重复输入，所以上图只是NFA，下面将它确定化： 下表由子集法将NFADFA:
转
换
为
由上表可知DFA为：
2．对下面的文法 G ： E->TE' E'->+E| ε T->FT' T' ->T| ε F-> PF' F'-> *F'| ε P->(E)|a|b|^
(1)计算这个文法的每个非终结符的 FIRST 集和 FOLLOW 集。 (2) 证明这个方法是 LL(1) 的。 (3) 构造它的预测分析表。 解：（1）计算这个文法的每个非终结符的FIRST集和FOLLOW集。 FIRST集合有：
FIRST(E)=FIRST(T)=FIRST(F)=FIRST(P)={(,a,b,^}; FIRST(E')={+,ε}
FIRST(T)=FIRST(F)=FIRST(P)={(,a,b,^}; FIRST(T')=FIRST(T)∪{ε}={(,a,b,^,ε}; FIRST(F)=FIRST(P)={(,a,b,^}; FIRST(F')=FIRST(P)={*,ε}; FIRST(P)={(,a,b,^}; FOLLOW集合有： FOLLOW(E)={),#};
FOLLOW(E')=FOLLOW(E)={),#};
FOLLOW(T)=FIRST(E')∪FOLLOW(E)={+,),#};//不包含ε FOLLOW(T')=FOLLOW(T)=FIRST(E')∪FOLLOW(E)={+,),#}; FOLLOW(F)=FIRST(T')∪FOLLOW(T)={(,a,b,^,+,),#};//不包含ε FOLLOW(F')=FOLLOW(F)=FIRST(T')∪FOLLOW(T)={(,a,b,^,+,),#}; FOLLOW(P)=FIRST(F')∪FOLLOW(F)={*,(,a,b,^,+,),#};//不包含ε (2)证明这个方法是LL(1)的。
13
各产生式的SELECT集合有：
SELECT(E->TE')=FIRST(T)={(,a,b,^}; SELECT(E'->+E)={+};
SELECT(E'->ε)=FOLLOW(E/)={),#} SELECT(T->FT')=FIRST(F)={(,a,b,^}; SELECT(T'->T)=FIRST(T)={(,a,b,^}; SELECT(T'->ε)=FOLLOW(T/)={+,),#}; SELECT(F->PF')=FIRST(P)={(,a,b,^}; SELECT(F'->*F')={*};
SELECT(F'->ε)=FOLLOW(F')={(,a,b,^,+,),#}; SELECT(P->(E))={(} SELECT(P->a)={a} SELECT(P->b)={b} SELECT(P->^)={^}
可见，相同左部产生式的SELECT集的交集均为空，所以文法G[E]是LL(1)文法。 (3)构造它的预测分析表。
文法G[E]的预测分析表如下：
3．已知 NFA= （ {x,y,z},{0,1},M,{x},{z} ），其中：
M(x,0)={z},M(y,0)={x,y},M(z,0)={x,z},M(x,1)={x}, M(y,1)= φ ,M(z,1)={y}, 构造相应的DFA并最小化。
解：根据题意有NFA图:
下
表
由
子
集
法
将
NFA
转
换
为
DFA
14
：
下面将该DFA最小化：
(1) 首先将它的状态集分成两个子集：P1={A,D,E},P2={B,C,F} (2) 区分P2:由于F(F,1)=F(C,1)=E,F(F,0)=F并且F(C,0)=C,所以F，C等价。由于F(B,0)=F(C,0)=C, F(B,1)=D,F(C,1)=E,而D，E不等价（见下步），从而B与C，F可以区分。有P21={C,F},P22={B}。 (3) 区分P1:由于A，E输入0到终态，而D输入0不到终态，所以D与A，E可以区分，有P11={A,E},P12={D}。 (4) 由于F(A,0)=B,F(E,0)=F,而B，F不等价，所以A，E可以区分。
(5) 综上所述，DFA可以区分为P={{A}，{B}，{D}，{E}，{C，F}}。所以最小化的DFA如下：
4． 已知文法为： S->a|^|(T) T->T,S|S
构造它的 LR(0)分析表。
解：加入非终结符S'，方法的增广文法为： S'->S S->a S->^ S->(T) T->T,S
T->S 下面构造它的LR(0)项目集规范族为：
15