P64 第三章习题.doc

64页12 将图a确定化 最小化10a,baa图a解：引入新的初态结点X和终态结点Y(X,Y不属于源非确定集)得图如下：YaX0 a,b a1列出状态转换矩阵如下所示：abA X,0,Y0,1,Y1B 0,1,Y0,1,Y1 C 10,Y D 0,Y0,1,Y1CDBADFA如下：aabbbba最少化：终态A,B,Da=A,BA,B,DA,B,Db=B,A,B,D 最少化为：10aba(b)将图b最少化b154320babaaabbaab图b解：终态0,1 a0,10,1 b=2,42,3,4,50,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,40代表0,1,2代表2,4,3代表3,5得最少化为：320ababba14.构造一个DFA，它接收=0,1上所有满足如下条件的字符串：每个1都有0直接跟在右边。解：构造正规式为：（0|10）*则可构造如下NFA：GBAFEDCqfq0010列出状态转换矩阵如下：01A q0,F,A,C, qf B,G,F,A,C, qfDB B,G,F,A,C, qfB,G,F,A,C, qfDC DE,G,F,A,B,C, qf D E,G,F,A,B,C, qf B,G,F,A,C, qfD则得DFA如下：CDBA0001101最少化得 A,B,D0=B A,B,D1=CA0C 1015.给定右线性文法G：S-0S|1S|1A|0BA-1C|1B-0C|0C-0C|1C|0|1求出一个与G等价的左线性文法。BSC解：由G得NFA=A1f0,1110,10,1000由NFA得左线性文法：GL=:A-1 B-0 C-A1|B0|C0|C1 f-A1|B0|C0|C181页1， 考虑下面文法G：S-a|(T)T-T,S|S(1)消除G的左递归(2)改写后的文法是否是LL(1)的？给出预分析表。解：(1) S-a|(T) T-ST T-,ST|(2) FIRSTFOLLOWSa,(#, , , ) Ta,()T, , )预分析表：a ( ) ， #SS-a S- S-(T)TT-ST T-ST T-STTT- T-,ST是LL(1)的。P812解：（1） firstfollowE(,a,b,#,)E+,#,)T(,a,b,+,#,)T(,a,b, +,#,)F(,a,b,(,a,b,+,#,)F*,(,a,b,+,#,)P(,a,b,*,(,a,b,+,#,)(2).略（3）（ab+*)#EETEETEETEETEEE+EEETTFTTFTTFTTFTTTTTTTTTTTTTFFPEFPEFPEFPEFFFFFFF*FFFPP(E)PaPbP 134页5文法 S-AS|bA-SA|a(1) 列出所有LR(0)项目(2) 构造LR(0)项目集规范族及识别活前缀的DFA(3) 该文法是SLR的么？若是构造它的SLR分析表。解：扩展文法：S-SSI6:A-SA A-SA A-a S-AS S-b S-AS|b A-SA|abI1: S-S A-SA A-a S-AS S-bI0 : S-S S-ASS-b A-SA A-aAaSI5: A-SA S-AS S-AS S-b A-SA A-aAa S bAI2 : S-ASS-AS S-b A-SA A-aI3 : S-bbbSI4 : A-aaa I7 : S-AS A-SA A-SAA-aS-AS S-bSAbAaa SbA(3)Follow FirstS # a,bS#,a,ba,bAa,ba,b冲突项目I中：有接受项目和移进冲突，可解决.a,bI5 , I7 存在移进，归约冲突，不可解决Follow(S) a b所以，该文法不是SLR的.证明下面的文法 S-AaAb|BbBa A- B-是LL(1)文法。不含左递归；First(1) First(2) =First(A) Follow(A) =该文法是LL(1)文法第七章1 给出下面表达式的逆波兰表示（后缀式）：a*(-b+c)a+b*(c+d/e)not A or not(C or not D)(A and B)or (not C or D) 后缀式分别为：ab-c+*abcde/+*+A not CD not or not orAB and C not D or or3. 请将表达式-（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), _)(3) (+, c, d)(4) (*,(2),(3)(5) (+, (1), c)(6) (-,(4),(5)间接代码： （1） （2） （3） （4） （1） （5） （6）四元式：（0）（+，a, b, T1）（1）（-，T1, _, T2）（2）（+， c, d, T3）（3）（*, T2, T3, T4）（4）（+，a, b, T5）（5）（+，T5, c, T6）（6）（-，T4,T6,T7）7.用7.5.1节的方法，把下面语句翻译成四元式序列： While AC and BD do If A=1 then C:=C+1 Else while AD do A:=A+2;100 （j, A,C,102）101 （j , _, _, 115）102 （j,B,D,104）103 （j ,_, _, 115）104 （j=,A, 1, 106）105 （j , _, _, 109）106 （+, C, 1, T1）107 （:=, T1,_,