第三四章习题课编译原理

第三、四章习题P64：7,8,9,12,14,15,20,补充题P81：1,2,3,4,52词法分析正规式自动机正规文法①②③④⑤⑥正规式正规文法NFADFA状态最小DFA词法分析器分裂法转换规则子集法分划法3正规式与正规文法的转化②:•令VT=∑•对任意正规式R选择一个非终结符Z生成规则ZR，并令S＝Z；•若a和b都是正规式，对形如Aab的规则转换成AaB和Bb；•在已转换的文法中，将形如Aa*b的规则进一步转换成AaA|b；•不断利用上上面后两条规则进行转换，直到每条规则最多含有一个终结符为止。①:•将每个非终结符表示成关于它的正规式方程，获得一个联立方程组。•依照求解规则：若x=x|(或x=x+)，则解为x=*若x=x|(或x=x+)，则解为x=*以及正规式的分配率、交换率和结合率求关于文法开始符号的正规式方程组的解。4正规式转化为NFA(1/2)(1)引进初始结点X和终止结点Y，把R表示成拓广转换图。如图XYR(2)分析R的语法结构，用如下规则对R中的每个基本符号构造NFA。•R＝，构造NFA如图：•R＝，构造NFA如图：XYXY•R＝a(a)，构造NFA如图：XYa5正规式转化为NFA(2/2)•若R是复合正规式，则按下图的转换规则对R进行分裂和加进新结，直至每个边上只留下一个符号（或）为止。ABr1r2ABr1Cr2代换为ABr1|r2ABr1r2代换为ABr1*ABC代换为r1整个分裂过程中，所有新结点均采用不同的名字，保留X，Y为全图唯一初态结点和终态结点6NFA确定化为DFA首先将从初态S出发经过任意条弧所能到达的状态所组成的集合作为M的初态S’，然后从S’出发，经过对输入符号a的状态转移所能到达的状态(包括读输入符号之前或之后所有可能的转移所能到达的状态)所组成的集合作为M的新状态，如此重复，直到不再有新的状态出现为止。从NFAN=(Q,,F,S,Z)构造等价的DFAM=(Q’,,F’,S’,Z’)的方法7DFA的化简将DFAM的状态集Q分成两个子集：终态集F和非终态集F，形成初始分划。对建立新的分划new。对的每个状态子集G进行如下变换：把G分划成新的子集，使得G的两个状态s和t属于同一子集，当且仅当对任何输入符号a，状态s和t转换到的状态都属于的同一子集。用G分划出的所有新子集替换G，形成新的分划new。如果new＝，则执行第（4）步；否则令＝new，重复第（2）步。分划结束，对分划中的每个状态子集，选出一个状态作代表，而删去其它一切等价的状态，并把射向其余状态的箭弧都改为射向作为“代表”的状态。81)增加新初态X，与所有原初态用ε相连，增加新终态Y，与所有原终态用ε相连，从而构成一个新的FAM’，它只有一个初态X和一个终态Y。2)在X与Y之间进行弧合并：ACBr1r2ABr1r2r2ACBr1r3ABr1r2ABr1|r2ABr1r2*r33)在X和Y之间的表达式即为所求的正规式R。代之以代之以代之以自动机转化为正规式9正规文法转化为自动机(1/2)设给定一个右线性正规文法G=(VN,VT,P,S)，则相应的有穷自动机M=(Q,,f,q0,Z)（1）将VN中的每一个非终结符视作M中的一个状态，并增加一个新终态D，且DVN，令Q=VN{D},Z={D},=VT,q0=S（2）对AaB（A,BVN,aVT{}），令f(A,a)=B。构造弧（3）对Aa（AVN,aVT{}），令f(A,a)=D。构造弧ABaADa10正规文法转化为自动机(2/2)设给定一个左线性正规文法G=(VN,VT,P,S)，则相应的有穷自动机M=(Q,,f,q0,Z)（1）将VN中的每一个非终结符视作M中的一个状态，并增加一个初始状态q0，且q0VN，令Q=VN{q0},Z={S},=VT(将文法G的开始符号S看成终态)（2）对ABa（A,BVN,aVT{}）令f(B,a)=A。构造弧（3）对Aa（AVN,aVT{}），令f(q0,a)=A。构造弧BAaq0Aa11自动机转化为正规文法(1/2)设给定有穷自动机M=(Q,,f,q0,Z)，按照下述方法可以从M构造出相应的右线性正规文法G=(VN,VT,P,S)，使得L(M)=L(G)(1)令VN=Q,VT=,S=q0(2)若f(A,a)=B且BZ时，则将规则AaB加到P中。(3)若f(A,a)=B且BZ时，则将规则AaBa或AaB,Bε加到P中。(4)若文法的开始符号S是一个终态，则将规则Sε加到P中。ABa注意:若终态无出弧，则去掉该非终结符起点开始，考虑出弧！12自动机转化为正规文法(1/2)设给定有穷自动机M=(Q,,f,q0,Z)，按照下述方法可以从M构造出相应的左线性正规文法G=(VN,VT,P,S)，使得L(M)=L(G)(1)令VN=Q,VT=,S=Z(2)若f(S,a)=A,则Aa|Sa(3)若f(A,a)=B,则BAa(A≠S)注意:若初态无入弧，则去掉该非终结符终点开始，考虑入弧！13习题7(1/4)7、构造下列正规式的相应的DFA1(0|1)*101解题步骤：1.由正规式R构造NFAN2.构造确定化后的DFA的状态矩阵3.生成确定化后的DFA的状态转换图4.化简DFA14习题7(2/4)由正规式构造NFA构造确定化后的DFA的状态矩阵Y234101X11010Q’10A{X}{0,1,2}B{0,1,2}{0,2,3}{0,2}C{0,2,3}{0,2,3}{0,2,4}D{0,2}{0,2,3}{0,2}E{0,2,4}{0,2,3,Y}{0,2}F{0,2,3,Y}{0,2,3}{0,2,4}15生成确定化后的DFA的状态转换图BFDE010C1100A101习题7(3/4)116化简DFAABlllFEC00l0lBFDE01C11100A10100首先M的状态分成两组：终态组{F}，非终态组{A,B,C,D,E}考察{A,B,C,D,E}，由于{A,B,C,D,E}1属于{B,C,F},它既不包含在{A,B,C,D,E}中也不包含在{F}之中，因此，应把{A,B,C,D,E}一分为二。因为状态E经1弧到达状态F，而状态A、B,C,D经1弧都到达{B,C}，因此，应把E分出来，形成{A,B,C,D}、{E}、{F}。{A,B,C,D}0属于{D,E},它不含在任何划分中，因为状态C经0弧到达状态E，而状态{A,B,D}经0弧都到达D，因此，应把C分出来，形成{A,B,D}、{C}、{E}、{F}。由于{A,B,D}1={B,C}，它不包含在任何划分之中，因此，应把{A,B,D}一分为二。因为状态B、D经1弧都到达{C}，经0弧都到达{D}因此，应把A分出来，形成{A}、{B,D}、{C}、{E}、{F}。{B,D}无法再分。至此，整个分划含有四组：{A}、{B,D}、{C}、{E}、{F}。每个组都不可再分。习题7(4/4)17习题8(1/3)8、给出下面正规表达式(1)以01结尾的二进制数串;(2)能被5整除的十进制整数;(3)包含奇数个1或者奇数个0的二进制数串;(7)不包含子串abb的由a和b组成的符号串的全体。18习题8(2/3)解：(1)末两位是01，其他位为0、1组成的任意的字符串。(a|b)*表示a、b组成的任意字符串。所以正规表达式为(0|1)*01。(2)①若是一位数，为0或5②若是多于一位的数，为(1|2|3|…|9)(0|1|2|…|9)*(0|5)所以正规表达式为(1|2|3|…|9)(0|1|2|…|9)*(0|5)|0|519习题8(3/3)(3)奇数个1：0*1(0|10*1)*奇数个0：1*0(1|01*0)*所以正则表达式为0*1(0|10*1)*|1*0(1|01*0)*(7)ab后只能跟a,所以可以是ab、a组成的任意符号串，即(a|ab)*。又若以b开始，所以正则表达式为b*(a|ab)*。20习题9(1/3)9、对下面的情况给出DFA以及正规表达式。(1){0，1}上的含有子串010的所有串。解：首先必须含有010，然后首尾为0、1组成的任意字符串，所以正规式为(0|1)*010(0|1)*。X15010Y2346001121习题9(2/3)Q’01A{X,5,1}{5,1,2}{5,1}B{5,1,2}{5,1,2}{5,1,3}C{5,1}{5,1,2}{5,1}D{5,1,3}{5,1,2,4,6,Y}{5,1}E{5,1,2,4,6,Y}{5,1,2,6,Y}{5,1,3,6,Y}F{5,1,2,6,Y}{5,1,2,6,Y}{5,1,3,6,Y}G{5,1,3,6,Y}{5,1,2,4,6,Y}{5,1,6,Y}H{5,1,6,Y}{5,1,6,Y}{5,1,6,Y}BHC01D1100A001GEF111000,1化简后的DFA：BA0ED0,10011122习题9(3/3)(2){0，1}上不含子串010的所有串。解：1*(0|111*)*1*X13Y425611661011ACBEGDFH10000000111111ABD01110化简后的DFADFANFA23习题12(1/3)12、将图3.18的(a)和(b)分别确定化和最少化。a,baa015042a3ba1abaaabbbb(b)(a)24习题12(2/3)a,baa01(a)Q’abA{0}{0,1}{1}B{0,1}{0,1}{1}C{1}{0}ababaCBAbaaAB255042a3ba1abaaabbbb(b)已经是确定化，对其最小化。1:{0,1},{2,3,4,5}{0,1}a={0,1}{0,1}b={2,4}{2,3,4,5}a={1,3,0,5}2:{0,1},{2,4},{3,5}{2,4}b={3,5}{3,5}b={2,4}baa02bb3a习题12(3/3)26习题14(1/2)14、构造DFA,接收{0，1}上所有满足每个1都有0直接跟在后面的字符串。解：正规表达式为(10|0)*27(10|0)*XY10120Q’01A{X,1,Y}{1,Y}{2}B{1,Y}{1,Y}{2}C{2}{1,Y}01010ABC100AC习题14(2/2)28习题15(1/3)15、给定右线性文法G：S→0S|1S|1A|0BA→1C|1B→0C|0C→0C|1C|1|0求出一个与G等价的左线性文法。29习题15(2/3)解：与文法G等价的自动机M=({S,A,B,C,D},{0,1},f,{S},{D})f(S,0)={S,B}f(S,1)={S,A}f(A,1)={C,D}f(B,0)={C,D}f(C,0)={C,D}f(C,1)={C,D}SA10,1B00,1100DC0,1130习题15(3/3)与文法G等价的左线性文法GL=({S,A,B,C,D},{0,1},f,{D})D→A1|B0|C0|C1C→A1|B0|C0|C1B→0|S0A→1|S1S→0|1|S0|S131习题20(1/3)20、假定有正规定义式A0→a|bA1→A0A0…An→An-1An-1考虑词形An(1)把An中所有简名都换掉，最终所得的正规式的长度是多少；(2)字集An的元素是什么？把它们非形式地表示成n的函数；(3)证明识别An的DFA只需要用2n+1个状态就足够了。32习题20(2/3)解:(1)An＝＞An-1An-1＝＞An-2An-2An-2An-2＝＞An-3An-3An-3An-3An-3An-3An-3An-3＝＞…＝＞即，所以长度为2n。(2)f(n)=121nA222nA323nAnA20nba2)|(nba2)|(33习题20(3/3)(3)用归纳法证明。当n=0时，只需要1个状态，即假设当n=k时成立，需要2k+1个状态；Ak+1=(a|b)(a|b)Sa