编译原理-第2章习题课

0YXCA 0YXCA DBEεε0X11Eε1DCBA 0X11Eε1DCBA 11NFA化为DFA：状态转换表：Q10{X}A{ABC}B{ABC}B{BCD}C{BC}D{BCD}C{BCD}C{BCE}E{BC}D{BCD}C{BC}D{BCE}E{BCDY}Y{BC}D{BCDY}Y{BCD}C{BCE}E11状态转换图：0110110110110YABCDE10初态0010ABBCDCCEDCDEYDYCE化简后得：001ABE Y11010011ABE Y1101001CC（2）(a|b)*(aa|bb)(a|b)*X12345YεεaaεbbababX12345Yεεaaεbbabab？NFA化为DFA：Qab{X12}{123}{124}{123}{1235Y}{124}{124}{123}{1245Y}{1235Y}{1235Y}{124Y}{1245Y}{123Y}{1245Y}{124Y}{123Y}{1245Y}{123Y}{1235Y}{124Y}aaX123456ababbabbabaabX123456ababbabbabaab化简得：1XY2baababab1XY2baababab0εε1BCDY0εε1BCDYεXAε10NFA到DFA：Q10{XAY}X{BCD}A{AY}B{BCD}A{CD}Y{AY}B{AY}B{BCD}A{AY}B{CD}Y{CD}Y{AY}BABYX10100110ABYX10100110化简后得；XA1001XA10012.将下图确定化和最小化。aa01a,b解:首先取A=ε-CLOSURE({0})={0},NFA确定化后的状态矩阵为:Q’abA{0}{0,1}{1}B{0,1}{0,1}{1}C{1}{0}NFA确定化后的DFA为：aaABabbC将A,B合并得:abACa3.构造一个DFA，它接受∑={0，1}上所有满足如下条件的字符串，每个1都有0直接跟在后边。000310XεεεεY310X1022用子集法确定化II0I1S01{X,0,1,3,Y}{0,1,3,Y}{2}{1,3,Y}{0,1,3,Y}{0,1,3,Y}{1,3,Y}{1,3,Y}{2}{2}/{2}12342244333DFA为0102110134304.给出NFA等价的正规式R。方法一：首先将状态图转化为BYCBAXε 1 1 ε 消去 得BYCBAX 0,1εYCAX11ε 消去其余结点YCAX、 0，1YX（0|1）*11 YXNFA等价的正规式为（0|1）*11方法二：NFA→右线性文法→正规式A→0A|1A|1BB→1CC→εA=(0+1)*11→(0|1)*115.试证明正规式（a|b）*与正规式（a*|b*）*是等价的。a证明：a(1)Y1X正规式(a|b)*的NFA为=>εεY1Xbab{X,1,y}{1,y}{1,y}{1,y}{1,y}{1,y}aA其最简DFA为A=>b(2)正规式（a*|b*）*的NFA为：3a3其最简化DFA为：aAεεA2Y1=>Xεε=>2Y1εεbbDFA的状态转换表：ab{x,1,2,3,y}{1,2,3,y}{1,2,3,y}{1,2,3,y}{1,2,3,y}{1,2,3,y}由于这两个正规式的最小DFA相同，所以正规式(a|b)*等价于正规式(a*|b*)*。6.设字母表∑={a,b},给出∑上的正规式R=b*ab(b|ab)*。试构造状态最小化的DFAM，使得L（M）=L（R）。X123YεεX123Yεεbab45εε6abbQab{X,1,2}1{3}2{1,2}3{3}2{4,5,Y}4{1,2}3{3}2{1,2}3{4,5,Y}4{6}5{5,Y}6{6}5{5,Y}6{5,Y}6{6}5{5,Y}6123123456abbababbbaXWYabbabXWYabbab（2）对应的右线性文法G=（{X,W,Y},{a,b},P,X）P:X→aW|bXW→bY|by→aW|bY|b3.8文法G[〈单词〉]为：〈单词〉-〉〈标识符〉|〈整数〉〈标识符〉-〉〈标识符〉〈字母〉|〈标识符〉〈数字〉|〈字母〉〈整数〉-〉〈数字〉|〈整数〉〈数字〉〈字母〉-〉A|B|C〈数字〉|->1|2|3（1）改写文法G为G’，使L(G’)=L(G)。（2）给出相应的有穷自动机。解：（1）令D代表单词，I代表标识符，Z代表整数，有G’（D）：D→I|ZI→A|B|C|IA|IB|IC|I1|I2|I3Z→1|2|3|Z1|Z2|Z3(2)左线性文法G’所对应的有穷自动机为：M=({S,D,I,Z},{1,2,3,A,B,C},f,S,{D})f:f(S,A)=I,f(S,B)=I,f(S,C)=If(S,1)=Zf(S,2)=Zf(S,3)=Zf(I,A)=If(I,B)=If(I,C)=If(I,1)=If(I,2)=If(I,3)=If(I,ε)=If(Z,1)=Zf(Z,2)=Zf(Z,3)=Zf(Z,ε)=D解:相应的正规式方程组为：S=0A+1B①A=1S+1②B=0S+0③将②，③代入①，得S=01S+01+10S+10④对④使用求解规则，得(01|10)*（01|10）为所求。X1Y2εab3aεX1Y2εab3aεbb正规式(a|ba)*b对应的DFA：Qab{X12}X{12}1{3Y}Y{12}1{12}1{3Y}Y{3Y}Y{12}1X1YaabaX1Yaababb化简后：XY1baaXY1baa方法二：P43右线性正规文法到有穷自动机的转换。文法S->aS|bA|bA->aS对应的NFA为：M=({S,A,D},{a,b},f,{S},{D})其中：f(S,a)=S,f(S,b)=A,f(S,b)=D,f(A,a)=S其NFA图为：aSbAabDNFA确定化后的状态矩阵为:Q’ab1{S}{S}{A,D}2{A,D}{S}φNFA确定化后的DFA为：ab12a3.5给出下述文法所对应的正规式：S=aA①A=bA+aB+b②B=aA ③将③代入②，得A=bA+aaA+b④将④用求解规则，得A=(b|aa)*b⑤,带入①得，S=a(b|aa)*b,故文法所对应的正规式为R=a(b|aa)*b。3.6给出与下图等价的正规文法G。aAaBbCbabDb答:该有穷自动机为:M=({A,B,C,D},{a,b},f,{A},{C,D})其中f(A,a)=B,f(A,b)=D,f(B,a)=φ,f(B,b)=C,f(C,a)=A,f(C,b)=D,f(D,a)=B,f(D,b)=D根据其转换规则，与其等价的正规文法G为G=（{A,B,C,D},{a,b},P,A）,其中P:A→aB|bDB→bCC→aA|bD|εD→aB|bD|ε3.12.解释下列术语和概念：(1)确定有穷自动机答：一个确定有穷自动机M是一个五元组M=（Q，Σ，f，S，Z），其中：Q是一个有穷状态集合，每一个元素称为一个状态；Σ是一个有穷输入字母表，每个元素称为一个输入字符；f是一个从Q*Σ到Q的单值映射；f（qi,a）=qj(qi,qj∈Q,a∈Σ)表示当前状态为qi，输入字符为a时，自动机将转换到下一个状态qj,qj称为qi的一个后继状态。我们说状态转换函数是单值函数，是指f（qi,a）惟一地确定了下一个要转移的状态，即每个状态的所有输出边上标记的输入字符不同。S∈Q，是惟一的一个初态；Z真包含于Q，是一个终态集。（2）非确定有穷自动机一个非确定有穷自动机M是一个五元组M=（Q，Σ，f，S，Z），其中：Q是一个有穷状态集合，每一个元素称为一个状态；当前输入字符惟一地确定下一个要转移的状态，即允许同一个状态对同一输入字符有不同的输出边。S包含于A，是非空初态集。Z真包含于Q，是一个终态集。（3）正规式和正规集有字母表Σ={a1,a2,…an}，在字母表Σ上的正规式和它所表示的正规集可用如下规则来定义：（1）φ是Σ是的正规式，它所表示的正规集是φ，即空集{}。（2）ε是Σ上的正规式，它所表示的正规集仅含一空符号串，即{ε}。（3）是Σ上的一个正规式，它所表示的正规集是由单个符号ai所组成，即{ai}。（4）e1和e2是Σ是的正规式，它们所表示的正规集分别为L(e1)和L(e2),则=1\*GB3①e1|e2是Σ上的一个正规式，它所表示的正规集为L(e1|e2)=L(e1)∪L(e2).=2\*GB3② e1e2是Σ上的一个正规式，它所表示的正规集为L(e1e2)=L(e1)L(e2).=3\*GB3③ (e1)*是Σ上的一个正规式，它所表示的正规集为L((e1)*)=L((e1))*.3．1构造下列正规式相应的DFA。1(0|1)*101(a|b)*(aa|bb)(a|b)*((0|1)*|(11))*(0|11*0)*3．2将下面图(a)和(b)分别确定化和最小化.aa01a,b(a)bba02b3aaaabba145b（b）3.3构造一个DFA，他接收∑={0，1}上所有满足如下条件的字符串，每个1都有0直接跟AaS3.5给出下述文法所对应的正规式：S->AaA->bA+aB+bB->aA3.6给出与下图等价的正规文法G。aAaBbCbabDb3.7给出与图3.29中的NFA等价的正规式R。3.8文法G[〈单词〉]为：〈单词〉〈标识符〉|〈整数〉〈标识符〉〈标识符〉〈字母〉|〈标识符〉〈数字〉|〈字母〉〈整数〉〈数字〉|〈整数〉〈数字〉〈字母〉A|B|C〈数字〉1|2|3改写文法G为G