計(jì)算理論課后習(xí)題答案(已修改)
2025-08-17 15:26 本頁面
【正文】 第一章 習(xí)題 1． 給定文法 G=({S,B,C,D,E},{0,1},P,S)， 其中 P： S→ABC ， AB→0AD ， AB→1AE ， AB→ε ， D0→0D ，D1→1D ， E0→0E ， E1→1E ， C→ε ， DC→B0C ，EC→B1C ， 0B→B0 ， 1B→B1 試寫出句子 01100110的派生過程。 解 ： S?ABC?0ADC?0AB0C?01AE0C?01A0EC ?01A0B1C?01AB01C?011AE01C?011A0E1C? 011A01EC?011A01B1C?011A0B11C?011AB011C ?0110AD011C?0110A0D11C?0110A01D1C? 0110A011DC?0110A011B0C?0110A01B10C? 0110A0B110C?0110AB0110C?01100110C?01100110 2． 設(shè)計(jì)下列各文法 G， 使得它們分別是： （ 1） G是個(gè)上下文無關(guān)文法 ， 且 L(G)={aibj ck ∣ i,j,k≥1}。 （ 2） G是個(gè)正規(guī)文法 ， 且 L(G)={aibj ck ∣ i,j,k≥1}。 （ 3） G是個(gè)上下文無關(guān)文法 ， 且 L(G)={ wwR∣ w∈ {0,1}+ }。 其中 wR是 w的逆轉(zhuǎn) ， 例 如 w=001, 則 wR=100. 解 ：設(shè)計(jì)一個(gè)文法 G要驗(yàn)證 ： 凡是符合要求的句子 G都能產(chǎn)生出來； G產(chǎn)生出來的所有句子都是符合要求的。 (1) G=({S,A,B,C},{a,b,c},P,S) P: S→ ABC , A→aA|a, B→bB|b,C→cC|c (2) G=({S,A,B,C},{a,b,c},P,S) P: S→a A , A→aA| bB, B→bB|cC, C→cC|ε (3) G=({S},{0,1},P,S) P: S→0S0|1S1|00|11 第二章 習(xí)題 1． 設(shè)計(jì)一個(gè)有限自動(dòng)機(jī) (FA) M， 使得 T(M)中的每個(gè)句 子 w同時(shí)滿足下面三個(gè)條件： 1) w∈ {a,b,}*； 2) |w|是 3的整數(shù)倍； 3) w以 a開頭 ， 以 b結(jié)尾 。 解： q0 q1 q3 q2 q4 a a,b a,b a,b b 2． 設(shè)計(jì)二個(gè) FA M1和 M2， 分別滿足 T(M1)={02i∣ i是自然數(shù) } T(M2)={02i+1∣ i=0,1,2,3,4,… } 解： M1 ： q0 q1 q3 0 0 0 q1 q0 0 0 q0 q1 0 0 M2 ： 3. 給定 NFA M1 =({p,q,r,s},{0,1},δ,p,{s})， 如下表所示。 構(gòu)造一個(gè) DFA M2， 使得 T(M1)=T(M2) 。 解 ：令 M2=(K’,∑, δ’, q0’,F’), 其中 K’?2K， K’中的元素是由 K的子集 {q1,q2,… ,qi}構(gòu)成 ， 但是要把子集 {q1,q2,… ,qi}作為的一個(gè)狀態(tài)看待 ， 因此把此子集寫成 [q1,q2,… ,qi]。 q0’=[q0] , F’={[q1,q2,… ,qi]|[q1,q2,… ,qi]∈ K’且 {q1,q2,… ,qi}∩F≠Φ} δ’ ： K’ ∑→K’ ， 對 ?[q1,q2,… ,qi]∈ K’, ? a∈ ∑， 有 δ’([q1,q2,… ,qi],a)=[p1,p2,… ,pj] 當(dāng)且僅當(dāng) δ({q1,q2,… ,qi},a)={p1,p2,… ,pj} δ 0 1 p {p,q} {p} q {r } {r} r {s} Φ s {s} {s} q0’=[p] , K’和 F’以后確定 。 δ’： δ 0 1 p {p,q} {p} q {r } {r} r {s} Φ s {s} {s} [p] 0 1 [p,q] [p] [p,q] [p,q,r] [p,r] [p,r] [p,q,s] [p] [p,q,r] [p,q,r,s] [p,r] [p,q,s] [p,q,r,s] [p,r,s] [p,r,s] [p,q,s] [p,s] [p,s] [p,q,s] [p,s] [p,q,r,s] [p,q,r,s] [p,r,s] K’={[p],[p,q],[p,r],[p,s],[p,q,r],[p,q,s],[p,r,s],[p,q,r,s]} F’ ={ [p,s],[p,q,s],[p,r,s],[p,q,r,s]} [p] [p,q] [p,r] [p,q,r] [p,q,s] [p,r,s] [p,s] [p,q,r,s] 0 1 0 0 0 0 0 0 1 0 1 1 1 1 1 1 εNFA M等價(jià)變換成 NFA M’。 a b c d e f ε 1 ε ε ε 0 1 0 否則－如果 ΦF)C L O U S U R E ( qεF}{qF{F 00 ???? ???δ’ ：對任何 q∈ K,任何 a∈ ∑, δ’(q,a)= (q,a) 。 解 ： M’=(K, ∑, δ’,q0 ,F’)， q0是 M的開始狀態(tài)，其中 ??公式 (1)：對于 ?q∈ K, , (q,ε)=εCLOSURE(q) 公式 (2)： 對于 ?q∈ K, ?w∈ ∑*, ?a∈ ∑, ?? ?? (q,wa)=εCLOSURE(δ( (q,w),a)) 因?yàn)?f?CLOSURE(a)={a,b}, 所以 F’=F={f} δ’ ： ?q∈ K,任何 a∈ ∑, a b c d e f ε 1 ε ε ε 0 1 0 ??δ’(q,a)= (q,a) 。 ??在計(jì)算 (q,a)時(shí)，要將 a理解成 a路徑 ！ ??例如 δ’(a,0)= (a,0)={c,e,d,b} 。 δ’: 0 1 abcdef {c,e,d,b} {d,b} Φ {d,b} {f} {f,d,b} {f} {d,b} {f} {f,d,b} Φ Φ 5． 化簡正規(guī)表達(dá)式 a(ε+aa)*(ε+a)b+b+φ(ab*+b)*。 解 ： 上式＝ a(aa)*(ε+a)b+b 其中 (aa)*(ε+a)代表集合： {ε,aa,aaaa,aaaaaa,… }{ε,a} = {ε,aa,aaaa,aaaaaa,… }?{a,aaa,aaaaa,…} ={ε,a,aa,aaa,aaaa,aaaaa,aaaaaa,… }={a}* 于是上式＝ aa*b+b=a+ b+b= (a++ε)b= a*b 6． 構(gòu)造一個(gè) FA M， 使得 T(M)的正規(guī)表達(dá)式為 01+((0+1)*1)*。 解 ： ， 找出基本單元： 0,1,01,1。 設(shè)計(jì)接收 這些基本單元的自動(dòng)機(jī)如下： q1 q2 0 q3 q4 1 q7 q8 1 q5 q6 0 q9 q10 1 ： （按照優(yōu)先權(quán)從高到低） 01+((0+1)*1)* q7 q8 1 q5 q6 0 q9 q17 1 q0 ε q15 q10 q16 q12 q2 q1 0 q3 q4 1 q14 q13
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1