編譯原理-第2章習題課

1、1.構(gòu)造正規(guī)式的 DFAQ10XAABC B0ABC BBCD CBC DBCD CBCD CBCE EBCDBCD CBC DBCE EBCDY YBC DBCDY YBCD CBCE E10ABBCDCCEDCDEYDYCE化簡后得:2(a|b)*(aa|bb)(a|b)*所以，DFA為:NFA化為DFAQabX 1 21 2 31 2 41 2 31 2 3 5 Y1 2 4 1 2 41 2 31 2 4 5 Y1 2 3 5 Y1 2 3 5 Y1 2 4 Y1 2 4 5 Y1 2 3 Y1 2 4 5 Y1 2 4 Y1 2 3 Y1 2 4 5 Y1 2 3 Y1 2 3 5

2、Y1 2 4 YQ10X A Y XB C D AA YBB C D AC DYA YBA YBB C D AA YBC DYC DYA YB3 0|11*0*£0NFA到 DFA0D£CA1BA101Y0B0化簡后得;12.將以下列圖確定化和最小化aaa,b解：首先取A=£ -CLOSURE(0)=0,NFA確定化后的狀態(tài)矩陣為Q'abA00,11B0,10,11C100NFA確定化后的DFA為:3.構(gòu)造一個DFA它承受刀=0 , 1上所有滿足如下條件的字符串,每個1都有0直接跟在后邊。解：按題意相應的正規(guī)表達式是0*(0 | 10)*0*構(gòu)造相應的DF

3、A首先構(gòu)造NFA為1 0用子集法確定化II 011S01X,0,1,3,Y0,1,3,Y21230,1,3,Y0,1,3,Y222321,3,Y/341,3,Y1,3,Y2443DFA為144.給出NFA等價的正規(guī)式R 方法一：首先將狀態(tài)圖轉(zhuǎn)化為NFA等價的正規(guī)式為0|1*11方法二：NFL右線性文法正規(guī)式A 0A|1A|1BB 1CC£A=0A+1A+1BB=1A=0A+1A+11A=(0+1)*11(0|1) *115. 試證明正規(guī)式a|b*與正規(guī)式a*|b*是等價的aNFA 為=>證明:正規(guī)式 a|bbabX, i,yi,yi,yi,yi,yi,ya其最簡DFA為=>

4、;b正規(guī)式a*|b*的NFA為:a其最簡化DFA為：DFA的狀態(tài)轉(zhuǎn)換表:abx,1,2,3,y1,2,3,y1,2,3,y1,2,3,y1,2,3,y1,2,3,y由于這兩個正規(guī)式的最小DFA一樣，所以正規(guī)式a|b*等價于正規(guī)式a*|b*。_ _ _ _ * *6. 設(shè)子母表刀=a,b,給出刀上的正規(guī)式R=bab(b|ab)。(1) 試構(gòu)造狀態(tài)最小化的DFAM使得L M =L F(2) 求右線性文法G,使LG=L解：(1)構(gòu)造NFA:b將其化為DFA轉(zhuǎn)換矩陣為：QabX,1,21321,23324,5,Y41,23321,234,5,丫4655,Y665r 5,y65,Y6655,Y6b再將其

5、最小化得2對應的右線性文法 G= X,W,Y,a,b,P,XP: X aW|bXWAbY|b y aW|bY|b3.8文法G單詞為：單詞-標識符|整數(shù)標識符-標識符字母|標識符數(shù)字|字母整數(shù)-數(shù)字|整數(shù)數(shù)字字母-A|B|C數(shù)字卜1|2|31改寫文法G為G ,使L(G' )=L(G)。2給出相應的有窮自動機。解：1令D代表單詞，I代表標識符，Z代表整數(shù)，有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

6、,C,f,S,D)f: f(S,A)=I, f(S,B)=I, f(S,C)=If(S,1)=Z f(S,2)=Z f(S,3)=Zf(I,A)=I f(I,B)=I f(I,C)=If(I,1)=I f(I,2)=I f(I,3)=I f(I,& )=If(Z,1)=Z f(Z,2)=Zf(Z,3)=Z f(Z,& )=D3.10給出下述文法所對應的正規(guī)式St 0A|1BA 1S|1Bt 0S|0解：相應的正規(guī)式方程組為：S=0A+1B A=1S+1B=0S+0將，代入，得S=01S+01+10S+10 對使用求解規(guī)那么，得01|10 * 01|10丨為所求。3.4給出文法

7、GS，構(gòu)造相應最小的DFAS->aS|bA|bA-> aS方法一：S=aS+bA+bA=aSS=aS+baS+b a+ba)*b即：S=(a|ba)*b正規(guī)式(a|ba)*b 對應的NFA正規(guī)式(a|ba)*b 對應的DFAQabX 1 2 X1 2 13Y Y1 2 11 2 13 Y Y3Y Y1 2 1中b方法二：P43右線性正規(guī)文法到有窮自動機的轉(zhuǎn)換。文法 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)=SNFA確定化后的DFA為: abNFA

8、確定化后的狀態(tài)矩陣為Q'ab1SS A,D2A,D S03.5給出下述文法所對應的正規(guī)式:S->aAA->bA+aB+bB->aA解：將文法改為：S=aAA=bA+aB+bB=aA將代入，得A=bA+aaA+b將用求解規(guī)那么，得A= (b|aa) *b ，帶入得，S= a(b|aa) *b, 故文法所對應的正規(guī)式為R= a(b|aa) *b。3.6給出與以下列圖等價的正規(guī)文法G答：該有窮自動機為：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

9、,a)=B, f(D,b)=D根據(jù)其轉(zhuǎn)換規(guī)那么，與其等價的正規(guī)文法G為G= A,B,C,D,a,b,P,A 丨，其中P : A taB|bD B 宀bC CaA|bD| £ D aB|b D £3.12.解釋以下術(shù)語和概念：(1)確定有窮自動機答：一個確定有窮自動機 M是一個五元組M=Q工，f , S, Z， 其中：Q是一個有窮狀態(tài)集合，每一個元素稱為一個狀態(tài)； 工是一個有窮輸入字母表，每個元素稱為一個輸入字符； f是一個從Q*2到Q的單值映射； f qi,a=q (q i,qj Q,aX)表示當前狀態(tài)為qi，輸入字符為a時，自動機將轉(zhuǎn)換到下一個狀態(tài)qj,qj 稱為q i的

10、一個后繼狀態(tài)。我們說狀態(tài)轉(zhuǎn)換函數(shù)是單值函數(shù)，是指f qi,a 惟一地確定了下一個要轉(zhuǎn)移的狀態(tài)，即每個狀態(tài)的所有輸出邊上標記的輸 入字符不同。S Q 是惟一的一個初態(tài)；Z真包含于Q, 是一2非確定有窮自動機一個非確定有窮自動機 M是一個五元組M=Q,X, f，S, Z，其中： Q是一個有窮狀態(tài)集合，每一個元素稱為一個狀態(tài)； 工是一個有窮輸入字母表，每個元素稱為一個輸入字符； 狀態(tài)轉(zhuǎn)換函數(shù)是一個多值函數(shù)。fqi ,a=某些狀態(tài)的集合(q i Q),表示不能由當前狀態(tài)、 當前輸入字符惟一地確定下一個要轉(zhuǎn)移的狀態(tài)，即允許同一個狀態(tài) 對同一輸入字符有不同的輸出邊。S 包含于A，是非空初態(tài)集。Z真包含于Q

11、3正規(guī)式和正規(guī)集有字母表工=a1,a2,an,在字母表 工 上的正規(guī)式和它所表示 的正規(guī)集可用如下規(guī)那么來定義：10是工是的正規(guī)式，它所表示的正規(guī)集是 0，即空集。2&是工上的正規(guī)式，它所表示的正規(guī)集僅含一空符號串，即汀。3是工上的一個正規(guī)式，它所表示的正規(guī)集是由單個符號 ai所組 成，即ai。4el和e2是工是的正規(guī)式，它們所表示的正規(guī)集分別為L(e1)和L(e2),那么 e1 | e2是工上的一個正規(guī)式，它所表示的正規(guī)集為L(e1 | e2)=L(e1) U L(e2). e1e2是工上的一個正規(guī)式，它所表示的正規(guī)集為L(e1e2)=L(e1)L(e2). (e1)*是工上的一個正

12、規(guī)式，它所表示的正規(guī)集為L(e1)*)=L(e1)*3. 1構(gòu)造以下正規(guī)式相應的DFA(1) 1 ( 0 | 1)*101(2) ( a | b )*( aa | bb )( a | b )*(3) ( 0 | 1 )* | ( 11 )*(4) ( 0 | 11*0 )*3. 2將下面圖(a)和(b)分別確定化和最小化aaa,baaababba 丿b3.3構(gòu)造一個DFA他接收刀=0 , 1上所有滿足如下條件的字符串，每個1都有0直接跟在右邊。3.4給出文法GS，構(gòu)造相應最小的 DFASaSbA | bAaS3.5給出下述文法所對應的正規(guī)式：S->AaA->bA+aB+bB->aA3.6給出與以下列圖等價的正規(guī)文法G3.8文法G單詞為：單詞標識符| 整數(shù)標識符標識符字母| 標識符數(shù)字|字母整數(shù)數(shù) _整數(shù)數(shù)字字母A | >B | C數(shù)字1 | 2->(1) 改寫文法G為G',使L(G' )=L(G).(2) 給出相應的有窮自動機。3.9試證明