资源描述：
《编译原理课后答案_第三版.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、三12将图a确定化最小化10a,baa图a解：引入新的初态结点X和终态结点Y(X,Y不属于源非确定集)得图如下：YaεεX0εεa,ba1列出状态转换矩阵如下所示：abA{X,0,Y}{0,1,Y}{1}B{0,1,Y}{0,1,Y}{1}C{1}{0,Y}øD{0,Y}{0,1,Y}{1}CDBADFA如下：aabbbba最少化：终态{A,B,D}a={A,B}∈{A,B,D}{A,B,D}b={B,}∈{A,B,D}∴最少化为：10aba(b)将图b最少化b154320babaaabbaab图b解：终态{0,1}a∈{0,1}{0,1}b={2,4}
2、∈{2,3,4,5}∴{0,1}不能再分非终态{2,3,4,5}a={0,1,3,5}{2,4}a={0,1}{2,4}b={3,5}{3,5}a={3,5}{3,5}b={2,4}0代表{0,1},2代表{2,4},3代表{3,5}得最少化为：320ababba14.构造一个DFA，它接收∑={0,1}上所有满足如下条件的字符串：每个1都有0直接跟在右边。解：构造正规式为：（0
3、10）*则可构造如下NFA：εGBAFEDCqfq00εεεεε10εε列出状态转换矩阵如下：01A{q0,F,A,C,qf}{B,G,F,A,C,qf}{D}B{B,G,F,
4、A,C,qf}{B,G,F,A,C,qf}{D}C{D}{E,G,F,A,B,C,qf}øD{E,G,F,A,B,C,qf}{B,G,F,A,C,qf}{D}则得DFA如下：CDBA0001101最少化得{A,B,D}0={B}{A,B,D}1={C}A0C1015.给定右线性文法G：S->0S
5、1S
6、1A
7、0BA->1C
8、1B->0C
9、0C->0C
10、1C
11、0
12、1求出一个与G等价的左线性文法。BSC解：由G得NFA=<{S,A,B,C}∪{f},{0,1},δ,S,{f}>A1f0,1110,10,1000由NFA得左线性文法：GL=<{0,1},{A,
13、B,C,f},f,ρ’>ρ’:A->1B->0C->A1
14、B0
15、C0
16、C1f->A1
17、B0
18、C0
19、C1四1.考虑下面文法G：S->a
20、^
21、(T)T->T,S
22、S(1)消除G的左递归(2)改写后的文法是否是LL(1)的？给出预分析表。解：(1)S->a
23、^
24、(T)T->ST’T’->,ST’
25、ε(2)FIRSTFOLLOWSa,^,(#,,,)Ta,^,()T’,,ε)预分析表：a^()，#SS->aS->^S->(T)TT->ST’T->ST’T->ST’T’T’->εT->,ST’是LL(1)的。五5．文法S->AS
26、bA->SA
27、a(1)列出所有LR
28、(0)项目(2)构造LR(0)项目集规范族及识别活前缀的DFA(3)该文法是SLR的么？若是构造它的SLR分析表。解：扩展文法：S’->SSI6:A->S·AA->SA·A->·aS->·ASS->·bS->AS
29、bA->SA
30、abI1:S’->S·A->S·AA->·aS->·ASS->·bI0:S’->·SS->·AS S->·bA->·SAA->·aAaSI5:A->SA·S->A·SS->·ASS->·bA->·SAA->·aAaSbAI2:S->A·S S->·ASS->·bA->·SAA->·aI3:S->b·bbSI4:A->a·aaI7:
31、S->AS·A->S·AA->·SA A->·aS->·ASS->·bSAbAaaSbA(3) FollowFirstS’#a,bS#,a,ba,bAa,ba,b冲突项目I１中：有接受项目和移进冲突，可解决. ＃a,bI5,I7存在移进，归约冲突，不可解决．∵Follow(S)∩a∩b≠○所以，该文法不是SLR的８.证明下面的文法S->AaAb
32、BbBaA->εB->ε是LL(1)文法。①不含左递归；②First(α1)∩First(α2)∩…=○③First(A)∩Follow(A)=○∴该文法是LL(1)文法七1．给出下面表
33、达式的逆波兰表示（后缀式）：a*(-b+c)a+b*(c+d/e)notAornot(CornotD)(AandB)or(notCorD)后缀式分别为：ab-c+*abcde/+*+AnotCDnotornotorABandCnotDoror3.请将表达式-（a+b）*(c+d)-(a+b+c)分别表示成三元式、间接三元式和四元式序列。三元式：(0)（+，a,b）(1)(-,(0),_)(2)(+,c,d)(3)(*,(1),(2))(4)（+，a,b）(5)(+,(4),c)(6)(-,(3),(5))间接三元式：(1)（+，a,b）(2)(-,(1)
34、,_)(3)(+,c,d)(4)(*,(2),(3))(5)(+,(1),c)(
