編譯原理-練習(xí)題講解

編譯原理作業(yè)評講教材：《編譯原理教程》胡元義等編著2003年第1版

CH.1補(bǔ)充作業(yè)設(shè)已有和，若L

S，寫出得到的過程，用T形圖表示。CLL,BCAS,ACBL,BL語言L語言B代碼S語言Ａ代碼A代碼L語言A代碼B代碼L語言L語言B代碼L語言Ａ代碼B代碼L語言B代碼B代碼CH.2作業(yè)教材上的習(xí)題2.3、2.4、2.5、2.7、2.9的主要問題是缺少過程。CH.2補(bǔ)充作業(yè)11.給出下面的正規(guī)表達(dá)式：

(1)以01結(jié)尾的二進(jìn)制數(shù)串。解：正規(guī)式(0|1)*01或(0*1*)*01(2)能被5整除的十進(jìn)制整數(shù)。解：正規(guī)式(0|1|2|3|4|5|6|7|8|9)*(0|5)或(0*1*2*3*4*5*6*7*8*9*)*(0|5)或(0|5)|(1|2|3|…|9)(0|1|2|3|…|9)*(0|5)或(+|-|ε)(0|1|2|3|…|9)*(0|5)

CH.3.練習(xí)題9(P64.)(3)英文字母組成的所有符號串，要求符號串中的字母依照字典序排列。解：正規(guī)式(a|A)*(b|B)*(c|C)*(d|D)*…(z|Z)*

或

A*B*C*D*…X*Y*Z*或

a*b*c*d*…x*y*z*(4){0,1}上的含有子串010的數(shù)字串(至少含一個)。解：正規(guī)式(0|1)*010(0|1)*

或(0*1*)*010(0*1*)*CH.2補(bǔ)充作業(yè)22.求正規(guī)式1(0|1)*101對應(yīng)的簡化的DFA。解1:正規(guī)式對應(yīng)的NFA:XY345110ε112ε10

I

I0I1{X}{1,3,2}{1,3,2}

{3,2}{3,4,2}{3,2}{3,2}{3,4,2}{3,4,2}{3,5,2}{3,4,2}{3,5,2}{3,2}{3,Y,4,2}{3,Y,4,2}{3,5,2}{3,4,2}

I

I0I1初01

123

223

343

425終543CH.2補(bǔ)充作業(yè)2正規(guī)式1(0|1)*101DFA:初始:{0,1,2,3,4}和{5}∵{0,1,2,3,4}0={2,4}{0,1,2,3,4}1={1,3,5}∴劃分為{0,1,2,3}和{4}∵{0,1,2,3}0={2,4}∴劃分為{0,1,2}和{3}∵{0,1,2}1={1,3}∴劃分為{0}和{1,2}∵{1,2}0={2}{1,2}1={3}最后劃分得5個子集:{0},{1,2},{3},{4},{5}105341101101010最小化DFA:105341101120100101CH.2補(bǔ)充作業(yè)22.求正規(guī)式1(0|1)*101對應(yīng)的簡化的DFA。解2:正規(guī)式對應(yīng)的NFA:04123110110

I

I0I1{0}初0{1}1{1}1{1}1{1,2}2{1,2}2{1,3}3{1,2}2{1,3}3{1}1{1,2,4}4{1,2,4}終4{1,3}3{1,2}210423110110010DFA:CH.2補(bǔ)充作業(yè)33.構(gòu)造一個DFA,它接受∑={0,1}上所有滿足如下條件的字符串:每個1都有0直接跟在右邊。

解：(1)正規(guī)式:(10|0)*或0*(100*)*或((10)*|0*)*YX10ε0ε1201001012

I

I0I1{X,1,Y}{1,Y}{2}

{1,Y}{1,Y}{2}{2}{1,Y}

I

I0I1初終0

12

終11

2

2

1

(3)確定化DFA:

CH.2補(bǔ)充作業(yè)3解：3.

(4)DFA的化簡:01001012初始:分為兩個組{0,1}和{2}∵{0,1}0={1}{0,1}1={2}∴{0,1}組不再分裂。最后劃分得2個子集:{0,1}和{2}選代表：0、2最小化的DFA見左圖。00021化簡的DFA:CH.3文法和語言作業(yè)P86.習(xí)題3.2、3.3、3.4、3.5、3.6(1)、3.7、2.7(2)，主要問題是沒按改過的題作，或作得不對。

3.3改寫為無二義文法G[S]：

S→aSb|AA→Ab|b3.4改寫為無二義文法G[S]：S→aS|a3.5(1)描述L={aibj|j>i≥1}的上下文無關(guān)文法可以是：

S→aSb|AbA→Ab|ab

或

S→aSb|aAbA→Ab|b或

S→ABA→aA|aB→bB|bb書上的文法是：

S→aSb|Sb|b有點錯！CH.3文法和語言作業(yè)P86.有的同學(xué)沒做3.5(1)和(3)題。3.5(2)改為“偶數(shù)個a和偶數(shù)個b”DFA如圖：abbBabCaaSAb用P36.的轉(zhuǎn)換規(guī)則把DFA轉(zhuǎn)換為正規(guī)文法G[S]：S→aA|bB|εA→aS|bC|aB→bS|aC|bC→bA|aB用P36.的轉(zhuǎn)換規(guī)則，把DFA轉(zhuǎn)換為正規(guī)文法G[A]：A→aA|bB|bB→aA|Bb|b|εB→ε可以刪去。進(jìn)一步簡化為G[S]：S→aS|bS|bCH.3文法和語言作業(yè)P86.