编译原理第2章习题课.docx

《编译原理第2章习题课.docx》由会员分享，可在线阅读，更多相关《编译原理第2章习题课.docx（28页珍藏版）》请在第一文库网上搜索。

1、1.构造正规式的DFAo状态转换表:Q10XAABCB0ABCBBCDCBCDBCDCBCDCBCEEBCDBCDCBCDBCEEBCDYYBCDBCDYYBCDCBCEE1010ABBCDCCEDCDEYDYCE化简后得:(3) (0|11*0) *0NFA 化为 DFA：QabX 1 21 2 31 2 41 2 3(1 2 3 5 Y(12 41 2 41 2 31 2 4 5 Y1 2 3 5 Y1 2 3 5 Y1 2 4 Y(1 2 4 5 Y)1 2 3 Y1 2 4 5 Y12 4 Y1 2 3 Y1 2 4 5 Y1 2 3 Y(1 2 3 5 Y1 2 4 YQ10X A

2、YXB C DAA YBB C DAc DYA YBA YBB C DAA YBc DYC DYA YB化简后得;2.将下图确定化和最小化。解:首先取A=CLOSURE(0) = 0, NFA确定化后的状态矩阵为:NFA确定化后的DFA为:将A,B合并得:a3 .构造一个DFA,它接受 = 0, 1上所有满足如下条件的字符串,每个1都有0直接跟在后边。10)*0*解：按题意相应的正规表达式是0*(0构造相应的DFA,首先构造NFA为用子集法确定化IIoI1S01X,0,l,3,Ykl,3,Y21230,l,3,Y)0,l,3,Y)222321,3,Y)/341,3,Y)1,3,Y)2443DF

3、A为4 .给出NFA等价的正规式Ro方法一：首先将状态图转化为0,1消去其余结点Y(0|1) *11NFA等价的正规式为（0|1） 41方法二：NFA-右线性文法f正规式AOA|1A|1BBTCCf eA=OA+1A+1BB=1A=OA+1A+11A= (0+1) *11(011)415 .试证明正规式（a|b） *与正规式（a*|b*） *是等价的。证明：a正规式 （a | b）引NFA 为二（X其最简DFA为X, l,y)l,y正规式（a*|b*） *的NFA为其最简化DFA为:DFA的状态转换表:x,1,2,3,y(1,2,3,y)(1,2,3,y)l,2,3,y)(1,2,3,y)l,

4、2,3,y)由于这两个正规式的最小DFA相同，所以正规式（a|b）*等价于正规式（a*|b*）*。6 .设字母表X=a,b,给出X上的正规式R=b*ab(b|ab)*o(1)试构造状态最小化的DFA M,使得L (M) =L (R)o(2)求右线性文法G,使L (G) =L (M)o解：(1)构造NFA：b将其化为DFA,转换矩阵为:Qab1，21,23320(4,5,Y)41,23321,234,5,Y)4655,Y66505,Y65,Y6655,Y6再将其最小化得:(2)对应的右线性文法G= (X,W,Y,a,b,P,X)P： XaW | bXWf bY |b y-aW |bY|b3.8文

5、法G单词为:单词-标识符|整数字母标识符-标识符字母|标识符数字整数-数字I整数数字字母-A|B|C(1)改写文法G为G，使L(G ) =L(G) o(2)给出相应的有穷自动机。M (1)令D代表单词，I代表标识符，Z代表整数，有G，(D)：Df I | ZIf A B C IA IB IC II 12 13Z-l | 2 i 3 | Z1 | Z2 i Z3(2)左线性文法X所对应的有穷自动机为：M=(S,D,I,Z, l,2,3,A,B,C,f,S, D)f： f(S,A)=I, f(S,B)=I,f(S,C)=If(S,l)=Z f(S,2)=Zf(I,A)=I f(I,B)=I8 )

6、If(S,3)=Zf(I,C)=If(I,3)=I f(I,f(Z,l)=Z f(Z,2)=Z f(Z,3)=Z f(Z, e)=D3. 10给出下述文法所对应的正规式。S-0AI1BA-1S|1B-OS|O解：相应的正规式方程组为:S=OA+1BA=1S+1B=OS+O将，代入，得S=01S+01+10S+10对使用求解规则，得(01110)* (01|10)为所求。3.4给出文法GS,构造相应最小的DFAoS-aS|bA|bA- aS方法一：.S=aS+bA+bA=aSS=aS+baS+b S= (a+ba)*b即:S= (a | ba) *b正规式(a|ba) *b对应的NFA：正规式(

7、a|ba) *b对应的DFA：QabX 1 2X1 213YY(1 2 11 213 YY3YY1 21*方法二：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图为:=NFA确定化后的状态矩阵为:Q，abss A,DA,D s63. 5给出下述文法所对应的正规式:S-aAA-bA+aB+bB-aA解：将文法改为：S=aAA二bA+aB+bB=aA将代入，得A=bA+aaA+b将用求解规则，得A= (b | aa)

8、*b ，带入得,S= a(b|aa) *b,故文法所对应的正规式为R= a(b|aa)*bo3. 6给出与下图等价的正规文法Go答：该有穷自动机为：f(B,b)=C,f(D,b)=DM=(A,B,C,D),a,b,f, A,C,D)其中 f (A,a)=B, f (A,b)=D,f (B,a) = 6 ,f(C,a)=A, f(C,b)=D,f(D,a)=B,根据其转换规则，与其等价的正规文法G为G= (A,B,C,D,a,b,P,A)，其中P ： AaB|bD B-bC CaA|bD| e D-aB|bD| e3. 12.解释下列术语和概念:(1)确定有穷自动机答：一个确定有穷自动机M是一个

9、五元组M=(Q, 2, f, S, Z),其中：、Q是一个有穷状态集合，每一个元素称为一个状态；2是一个有穷输入字母表，每个元素称为一个输入字符;f是一个从Q*2到Q的单值映射；.f (q ,a) =q (q ,q Q,a 2)表示当前央态为q ,输入李符为a时，自动机将转换到下一个状态q ,q称为q的一个后继状表。我们说状态转换函数是单值函数，是指f (q ,k)J1 1惟一地确定了下一个要转移的状态，即每个状态的所有输出边上标记的输入字符不同。.SeQ,是惟一的一个初态;Z真包含于Q,是一个终态集。(2)非确定有穷自动机一个非确定有穷自动机M是一个五元组M= (Q, S, f, S, Z)

10、,其中:Q是一个有穷状态集合，每一个元素称为一个状态；.2是一个有穷输入字母表，每个元素称为一个输入字符；状态转换函数是一个多值函数。f (q. ,a)=某些状态的集合 (q.WQ),表示不能由当前状态、当前输入与符惟一地确定下一个要转次的状态，即允许同一个状态对同一输入字符有不同的输出边。.S 包含于 A,是非空初态集。Z真包含于Q,是一个终态集。(3)正规式和正规集有字母表2 = al,a2,an,在字母表2上的正规式和它所表示的正规集可用如下规则来定义:(1)。是2,是的正规式，它所表示的正规集是6,即空集屋(2) 是2上的正规式，它所表示的正规集仅含一空符号串，即.。(3)是2上的一个

11、正规式，它所表示的正规集是由单个符号ai所组成，即ai。.(4) el和e2是2是的正规式，它们所表示的正规集分别为L(el)和L(e2),则el | e2是2上的一个正规式，它所表示的正规集为L(el | e2)=L(el) UL(e2).ele2是2上的一个正规式，它所表示的正规集为L(ele2)=L(el)L(e2).(el)*是2上的一个正规式，它所表示的正规集为L(el)*) =L(el)*.3. 1构造下列正规式相应的DFA。(1) 1 ( 0 | 1)*101(2) ( a | b )*( aa | bb ) ( a | b )*(3) ( 0 | 1 )* | ( 11 )*(4) ( 0 | 11*0 )*1.2 将下面图(a)和(b)分别确定化和最小化.=(a)(b)1.3 构造一个DFA,他接收 = 0, 1上所有满足如下条件的字符串，