詞法分析習題

1、詞法分析補充習題1. 構(gòu)造與正規(guī)式(a|ba)*等價的狀態(tài)最少的 DFA。2. 構(gòu)造與正規(guī)式(a|b)*a(a|b)等價的狀態(tài)最少的 DFA。3. 構(gòu)造與正規(guī)式(a|b)* aa等價的狀態(tài)最少的DFA。1.解答：(1)構(gòu)造NFA如圖1所示：(2)NFA確定化為DFA的過程如下表所示:IIaIbS, A, ZA, ZBA, ZA, ZBBA, Z 為重新標注的狀態(tài)號。畫出相應的狀態(tài)圖如圖2所示。圖 2 (a | ba) * 的 DFA(3) DFA最小化首先得到兩個子集 K1 = 3和K2 = 1, 2?？疾霮2,由于1 , 2a = 2? K2 , 1 , 2b = 3? K1，所以K2不可再

2、分。用1來代表K2 并刪除3，得到最小化DFA的狀態(tài)圖，圖3所示.圖3正規(guī)式(a | b a) *的最小化DFA2解答(1)構(gòu)造NFA,見圖1(2) NFA確定化為DFA的過程表和相應 DFA的狀態(tài)圖，見圖2IIaIbS, A, BA, B, CA, BA, B, CA, B, C, ZA, B, ZA, BA, B, CA, BA, B, C, ZA, B, C, ZA, B, ZA, B, ZA, B, CA, B 為重新標注的狀態(tài)號。畫出相應的狀態(tài)圖如圖2所示。圖 2 正規(guī)式(a|b)*a (a|b)的 DFA(3)將DFA最小化并得到最小化的狀態(tài)圖，見圖3首先進行初始劃分得到兩個子集：

3、Ki = 1,2,3和K2 = 4, 5考察Ki :因1,2,3a=2,4? Ki，也？ K2,所以1,2,3可被重新劃分。由于狀態(tài) 1和狀態(tài)3 輸入a都到達狀態(tài)2,輸入b都到達狀態(tài)3，而狀態(tài)2輸入a到達狀態(tài)4,輸入b到達狀態(tài) 5，所以將K1分割成：Kii = 1,3和Ki2 = 2目前劃分得到的子集為：Kii = 1,3 , K12 = 2, K = 4，5考察 Ki仁1,3a=2? Ki, 1,3b=3? Ki，所以1,3無需重新劃分。考察K2：因4, 5 a=4,2? Kii,?K12,?K2,所以K2可被重新劃分。將K2分割成：K2i =4，K22=5。目前劃分得到的子集為：Kii=i

4、, 3, K12 = 2, K21 =4, K22=5最后，令狀態(tài)1代表Kii，并刪除3,最小化DFA的狀態(tài)圖如下所示：圖3正規(guī)式(a|b)*a (a|b)的最小化 DFA注(思考)：本題圖1中的&可省去，便可簡化 DFA的構(gòu)建過程，見題 3。3.解答：(1)構(gòu)造NFA如圖1所示:圖1 (a | b) *aa的(NFA虛框內(nèi)去掉)(2) NFA確定化為DFA的過程如下表所示:IIalbS, A A, BAA, BA,B, ZAAA, BAA, B, ZA,B, ZA相應的狀態(tài)圖如圖2所示。圖 2 (a | b) *aa 的 DFA(3) DFA最小化首先得到兩個子集 K1 = 1,2,3和K2 = 4?？疾霮1:由于1,2,3a = 1,2 , 4? K1,也？ K2,所以K1可需要被分割。又因為1,3a = 2, 1,3b = 3，所以將原狀態(tài)集合分割成以下子集：K11=2, K12=1, 3。目前劃分得到的子集為：K11=2, K12=1, 3, K2 = 4考察K12: 1,3a = 2? K1, 1,3b = 3? K1，