編譯原理習(xí)題集(已修改)
2025-08-05 03:01 本頁面
【正文】 第二章（2）{anbmcp|n,m,p≥0}解： G(S) ：S→aS|X,X→bX|Y,Y→cY|ε（3）{an bn|n≥0}∪{ dn|n≥0}解： G(S)：S→X,S→Y,X→aXb|, Y→cYd| }（5）任何不是以0 打頭的所有奇整數(shù)所組成的集合解：G(S)：S→J|IBJ,B→0B|IB|ε,I→J|2|4|6|8, J→1|3|5|7|9}（6）（思考題）所有偶數(shù)個0 和偶數(shù)個1 所組成的符號串集合解：對應(yīng)文法為 S→0A|1B|ε，A→0S|1C B→0C|1S C→1A|0B（2）S→SS S→1A0 A→1A0 A→ε解：L(G)={1n10n11n20n2 … 1nm0nm |n1,n2,…,nm≥0；且n1,n2,…nm 不全為零}該語言特點是：產(chǎn)生的句子中，0、1 個數(shù)相同，并且若干相接的1 后必然緊接數(shù)量相同連續(xù)的0。（5）S→aSS S→a解：L(G)={a(2n1)|n≥1}可知：奇數(shù)個a5. (1) 解：由于此文法包含以下規(guī)則：AA→ε，所以此文法是0 型文法。：(1)aacb 是文法G[S]中的句子，相應(yīng)語法樹是：最右推導(dǎo)：S=aAcB=aAcb=aacb最左推導(dǎo)：S=aAcB=aacB=aacb（3）aacbccb 不是文法G[S]中的句子aacbccb 不能從S推導(dǎo)得到時，它僅是文法G[S]的一個句型的一部分，而不是一個句子。：最右推導(dǎo):(1) S=AB=AaSb=Aacb=bAacb=bbAacb=bbaacb上面推導(dǎo)中，下劃線部分為當(dāng)前句型的句柄。對應(yīng)的語法樹為：短語直接短語句柄a1 對A1√√b1a1 對 A2b2b1a1 對A3c 對S1√a2cb3對Bbbaacb 對 S2第三章3 假設(shè)M:人 W:載狐貍過河，G:載山羊過河，C:載白菜過河6 根據(jù)文法知其產(chǎn)生的語言是L={ambnci| m,n,i≧1}可以構(gòu)造如下的文法VN={S,A,B,C}, VT={a,b,c}P={ S →aA, A→aA, A→bB, B→bB, B→cC, C→cC, C→c}其狀態(tài)轉(zhuǎn)換圖如下:7 (1) 其對應(yīng)的右線性文法是:A →0D, B→0A,B→1C,C→1|1F,C→1|0A,F→0|0E|1A,D→0B|1C,E→1C|0B(2) 最短輸入串011(3) 任意接受的四個串： 011,0110,0011,000011(4) 任意以1 打頭的串.9．對于矩陣(iii)(1) 狀態(tài)轉(zhuǎn)換圖：(2) 3型文法（正規(guī)文法）S→aA|a|bB A→bA|b|aC|a B→aB|bC|b C→aC|a|bC|b(3)用自然語言描述輸入串的特征以a 打頭，中間有任意個（包括0個）b,再跟a,最后由一個a,b 所組成的任意串結(jié)尾或者以b 打頭，中間有任意個（包括0個）a,再跟b,最后由一個a,b 所組成的任意串結(jié)尾。12 (1)確定化：ab[S] S[S,A] A[S,A] A[S,A] A[A,B] [A,B] [B] [A,B] [B] [B] 以上為第一次作業(yè)最小化：186。0186。 {S,A} {B,C}因為 {S}b=φ {A}b={B} 所以 {S,A}={S}{A}因為 {C}b=φ {B}b={B
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1