北京郵電大學(xué)-形式語言與自動機(jī)-課后習(xí)題答案

北京郵電大學(xué)-形式語言與自動機(jī)-課后習(xí)題答案

形式語言與自動機(jī)第二章4.找出右線性文法，能構(gòu)成長度為1至5個字符且以字母為首的字符串。答：G={N,T,P,S}，其中N={S,A,B,C,D}，T={x,y}，其中x∈{所有字母}，y∈{所有的字符}，P如下：S→xSS→xAA→yAA→yBB→yBB→yCC→yCC→yDD→y6.構(gòu)造上下文無關(guān)文法能夠產(chǎn)生L={ω/ω∈{a,b}*且ω中a的個數(shù)是b的兩倍}。答：G={N,T,P,S}，其中N={S}，T={a,b}，P如下：S→aabSS→abaSS→baaSS→εS→aabSSS→aAsbSS→aSabSS→SaabS→abaSSS→abSaSS→aSbaSS→SabaS→baaSSS→baSaSS→bSaaSS→Sbaa7.找出由下列各組生成式產(chǎn)生的語言（起始符為S）(1)S→SaSS→b(2)S→aSb(3)S→aS→aEE→aS答：（1）L={b(ab)n/n≥0}或者L={(ba)nb/n≥0}；（2）L={anbn/n≥0}；（3）L={a2n+1/n≥0}。第三章1.下列集合是否為正則集，若是正則集寫出其正則式。（1）含有偶數(shù)個a和奇數(shù)個b的{a,b}*上的字符串集合。（2）含有相同個數(shù)a和b的字符串集合。（3）不含子串a(chǎn)ba的{a,b}*上的字符串集合。答：（1）是正則集，正則式為(a(aa)*b(bb)*)*；（2）不是正則集；（3）是正則集，正則式為(b+a)*ba?(b+a)*。4.對下列文法的生成式，找出其正則式。（1）G=({S,A,B,C,D},{a,b,c,d},P,S)，生成式P如下：S→aASS→BA→abSAA→bBB→bBB→cCC→DDD→d（2）G=({S,A,B,C,D},{a,b,c,d},P,S)，生成式P如下：S→aASS→BA→cCAA→bBB→bBBB→aC→DCC→abBD→d答：（1）正則式為ad*(b+c(aa)*bb*)*；（2）正則式為a(c(aa)*+b)*d*.9.對應(yīng)圖(a)(b)的狀態(tài)轉(zhuǎn)換圖寫出正則表達(dá)式。（圖略）(1)由圖可知q=aq+bq1+a+εq1=aq2+bq1q=aq+bq1+a=>q1=abq1+bq1+aaq+aa=(b+ab)q1+aaq+aa=(b+ab)*(aaq+aa)=>q=aq+b(b+ab)*(aaq+aa)+a+ε=q(a+b(b+ab)*aa)+b(b+ab)*aa+a+ε(2)由圖可知p=ap+bp+bq1+ap2+bq1=>p=(a+b)p+bq1=>p=(a+b)*bq+(a+b)*a(a+b)*bq+(a+b)*a(a+b)*a(a+b)*bq+...=(a+b)*(a(a+b)*bq)+bq=>p=(a+b)*a(a+b)*bq+bq.修正格式錯誤和刪除明顯有問題的段落后，文章如下：給定以下表達(dá)式：$(a+b(b+ab)\cdotaa)\cdot((b+ab)\cdotaa+a+\epsilon)\\=(a+b(b+ab)\cdotaa)\cdot((b+ab)\cdotaa+a)$將其化簡得到：$q=aq_1+bq_2+a+bq_1=aq_1+baq_1+bbq_2+ba+bq_2\\=(ba)\cdot(aq_1+bbq_2+ba+b)+(ab)\cdot(aaq_2+bq_2+ab+a)\\=q_2\cdot(aa)+q_1\cdot(ab)+q_1\cdot(ba)+q_2\cdot(ab)+q_1\cdot(a)+q_2\cdot(ba)+a+b\\=[a(ba)\cdot(a+bb)+b(ab)\cdot(aa+b)]\cdot[a(ba)\cdot(ba+b)+b(ab)\cdot(ab+a)+a+b]$現(xiàn)在考慮構(gòu)造接受下列語言的DFA：（1）含有3個連續(xù)b的所有字符串集合（2）以aa為首的所有字符串集合（3）以aa結(jié)尾的所有字符串集合解：（1）構(gòu)造DFAM=({q,q1,q2,q3},{a,b},ζ,q,{q3})，其中ζ如下：$\zeta(q,a)={q,q1},\zeta(q,b)={q}\\\zeta(q1,a)={q2},\zeta(q1,b)={q2}\\\zeta(q2,a)={q3},\zeta(q2,b)=\varnothing\\\zeta(q3,a)={q3},\zeta(q3,b)={q3}$（2）構(gòu)造DFAM=({q,q1,q2},{a,b},ζ,q,{q2})，其中ζ如下：$\zeta(q,a)={q1,q2},\zeta(q,b)=\varnothing\\\zeta(q1,a)={q2},\zeta(q1,b)={q1,q2}\\\zeta(q2,a)=\varnothing,\zeta(q2,b)=\varnothing$（3）構(gòu)造DFAM=({q,q1,q2},{a,b},ζ,q,{q2})，其中ζ如下：$\zeta(q,a)={q1,q2},\zeta(q,b)=\varnothing\\\zeta(q1,a)={q2},\zeta(q1,b)={q1}\\\zeta(q2,a)=\varnothing,\zeta(q2,b)=\varnothing$最后，給定一個NFAM，我們可以構(gòu)造一個等價的DFAM。具體地，對于一個NFAMM=(Q,Σ,ζ,S,F)，我們可以構(gòu)造一個DFAMM'=(Q',Σ,ζ',S',F')，其中：-$Q'=2^Q$，即M'的狀態(tài)集合是M的狀態(tài)集合的所有子集。-$\zeta'(T,a)=\bigcup_{q\inT}\zeta(q,a)$，即M'中從狀態(tài)集合T開始，經(jīng)過一次輸入字符a可以到達(dá)的所有狀態(tài)的集合。-$S'=\{S\}$，即M'的初始狀態(tài)是M的初始狀態(tài)。-$F'=\{T\subseteqQ\midT\capF\neq\varnothing\}$，即M'的接受狀態(tài)是M的狀態(tài)集合中至少有一個接受狀態(tài)的子集。15.對下面矩陣表示的ε-NFA：$$\begin{matrix}&a&b&c&\epsilon\\p&\{p\}&\{p,q\}&\{p,q,r\}&\emptyset\\q&\emptyset&\{p,q,r\}&\{q,r\}&\emptyset\\r&\emptyset&\emptyset&\emptyset&\{r\}\end{matrix}$$（1）給出該自動機(jī)接受的所有長度為3的串。（2）將此ε-NFA轉(zhuǎn)換為沒有ε的NFA。答：（1）可被接受的串共23個，分別為aac、abc、acc、bac、bbc、bcc、cac、cbc、ccc、caa、cab、cba、cbb、cca、ccb、bba、aca、acb、bca、bcb、bab、bbb、abb。（2）ε-NFA：$M=({p,q,r},{a,b,c},\zeta,p,r)$，其中$\zeta$如表格所示。因為$\epsilon$-closure($p$)=?，則設(shè)不含$\epsilon$的NFA$M_1$=(${p,q,r}$,{a,b,c},$\zeta_1$,$p$,$r$)。$\zeta_1(p,a)=\zeta'(\zeta(p,\epsilon),a)=\epsilon$-closure($\zeta(\epsilon$-closure($p$),$a$))={$p$}。$\zeta_1(p,b)=\zeta'(\zeta(p,\epsilon),b)=\epsilon$-closure($\zeta(\epsilon$-closure($p$),$b$))={$p,q$}。$\zeta_1(p,c)=\zeta'(\zeta(p,\epsilon),c)=\epsilon$-closure($\zeta(\epsilon$-closure($p$),$c$))={$p,q,r$}。$\zeta_1(q,a)=\zeta'(\zeta(q,\epsilon),a)=\epsilon$-closure($\zeta(\epsilon$-closure($q$),$a$))={$p,q$}。$\zeta_1(q,b)=\zeta'(\zeta(q,\epsilon),b)=\epsilon$-closure($\zeta(\epsilon$-closure($q$),$b$))={$p,q,r$}。$\zeta_1(q,c)=\zeta'(\zeta(q,\epsilon),c)=\epsilon$-closure($\zeta(\epsilon$-closure($q$),$c$))={$p,q,r$}。$\zeta_1(r,a)=\zeta'(\zeta(r,\epsilon),a)=\epsilon$-closure($\zeta(\epsilon$-closure($r$),$a$))={$p,q,r$}。$\zeta_1(r,b)=\zeta'(\zeta(r,\epsilon),b)=\epsilon$-closure($\zeta(\epsilon$-closure($r$),$b$))={$p,q,r$}。$\zeta_1(r,c)=\zeta'(\zeta(r,\epsilon),c)=\epsilon$-closure($\zeta(\epsilon$-closure($r$),$c$))={$p,q,r$}。圖示如下：（$r$為終止?fàn)顟B(tài)）$$\begin{matrix}&a&b&c\\p&\{p\}&\{p,q\}&\{p,q,r\}\\q&\{p,q\}&\{p,q,r\}&\{p,q,r\}\\r&\{p,q,r\}&\{p,q,r\}&\{p,q,r\}\end{matrix}$$16.設(shè)$NFA_M=({q,q_1},{a,b},\zeta,q,{q_1})$，其中$\zeta$如下：$\zeta(q,a)=\{q,q_1\}$，$\zeta(q,b)=\{q_1\}$，$\zeta(q_1,a)=\emptyset$，$\zeta(q_1,b)=\{q,q_1\}$。構(gòu)造相應(yīng)的$DFA_M$。答：$DFA_M=({q,q_1},{a,b},\delta,q_0,F)$，其中$q_0=\{q\}$，$F$為所有包含$q_1$的集合。$\delta(\{q\},a)=\zeta(q,a)=\{q,q_1\}$，$\delta(\{q\},b)=\zeta(q,b)=\{q_1\}$，$\delta(\{q,q_1\},a)=\zeta(q,a)\cup\zeta(q_1,a)=\{q,q_1\}$，$\delta(\{q,q_1\},b)=\zeta(q,b)\cup\zeta(q_1,b)=\{q,q_1\}$，$\delta(\{q_1\},a)=\zeta(q_1,a)=\emptyset$，$\delta(\{q_1\},b)=\zeta(q_1,b)=\{q,q_1\}$。轉(zhuǎn)移表如下：$$\begin{matrix}&a&b\\\{q\}&\{q,q_1\}&\{q_1\}\\\{q,q_1\}&\{q,q_1\}&\{q,q_1\}\\\{q_1\}&\emptyset&\{q,q_1\}\end{matrix}$$狀態(tài)圖如下：$$\begin{matrix}&&\{q\}&&\\&\nearrow_a&&\nearrow_b&\\\{q,q_1\}&&&&\{q_1\}\end{matrix}$$18.構(gòu)造米蘭機(jī)和摩爾機(jī)。米蘭機(jī)（Myhillautomaton）是一種有限狀態(tài)自動機(jī)，其狀態(tài)集合為Q，輸入字母表為Σ，轉(zhuǎn)移函數(shù)為δ，起始狀態(tài)為q0，接受狀態(tài)集合為F。其中，對于任意q∈Q和a∈Σ，δ(q,a)∈Q。如果一個字符串w能夠使得自動機(jī)從起始狀態(tài)q0經(jīng)過一系列轉(zhuǎn)移后到達(dá)接受狀態(tài)集合F中的某一個狀態(tài)，則稱該自動機(jī)接受字符串w。摩爾機(jī)（Mooremachine）是一種有限狀態(tài)自動機(jī)，其狀態(tài)集合為Q，輸入字母表為Σ，輸出字母表為Γ，轉(zhuǎn)移函數(shù)為δ，輸出函數(shù)為λ，起始狀態(tài)為q0。其中，對于任意q∈Q和a∈Σ，δ(q,a)∈Q，λ(q)∈Γ。如果一個字符串w能夠使得自動機(jī)從起始狀態(tài)q0經(jīng)過一系列轉(zhuǎn)移后到達(dá)某一狀態(tài)q∈Q，并輸出該狀態(tài)對應(yīng)的λ(q)，則稱該自動機(jī)輸出字符串w。構(gòu)造米蘭機(jī)和摩爾機(jī)的關(guān)鍵是確定狀態(tài)集合、輸入字母表、輸出字母表、轉(zhuǎn)移函數(shù)和輸出函數(shù)。在實際應(yīng)用中，可以根據(jù)具體問題的特點來設(shè)計自動機(jī)。1A4A4|A2A5A4|A2A6,A2→bA5,②對于A3→A3A3b,用A3→A1a|A3A3b|a代入得A3→A1aA3|A3A3bA3|aA3|A3A3b,用引理4.2.4,變化為A3→aA3|bA3A3|aA3A3bA3,A3→a|A3A3b,③將A1生成式代入A2生成式得A2→bA5,A5→a,④將A1生成式代入A3生成式得A3→aA3|bA3A3|a|A3A3b,⑤由此得出等價的Greibach范式文法：G2=({A1,A2,A3,A4,A5},{a,b},P2,A1),其中生成式P2如下：A1→A3A4|A2A5,A2→bA5,A3→aA3|bA3A3|a|A3A3b,A4→b,A5→a.由于沒有提供原始文章，無法確定哪些是格式錯誤和明顯有問題的段落。以下是對給出的等價Greibach范式文法的改寫：文法G1=({S,D,D'},{a,b},P1,S)，其中生成式P1如下：A1→A3A4|A2A5，A2→A3A4A4|b|A3A4A4A2'|bA2'，A3→bA5A5|bA2'A5A5|a|bA5A5A3'|bA2'A5A5A3'|aA3'，A4→b，A5→a，A6→bA5A5A4A4A5|bA2'A5A5A4A4A5|aA4A4A5|bA5A5A3'A4A4A5|bA2'A5A5A3'A4A4A5|aA4A4A2'A5|bA5A5A3'A4A4A2'A5|bA2'A5A5A3'A4A4A2'A5|aA3'A4A4A2'A5|bA2'A5|bA5，A7→bA5A5A4|bA2'A5A5A4|aA4|bA5A5A3'A4|bA2'A5A5A3'A4。說明：將每個非終結(jié)符的產(chǎn)生式分成多行，使得每行都不會太長。同時，將產(chǎn)生式中的'|'符號改寫為'或'，使得更加易讀。Therearealotofformattingerrorsinthistext,soIwillcleanitupandrewriteeachparagraphinamorereadableway.Rewrittentext:Thereisnotextprovidedtoworkwith.Pleaseprovidetheoriginaltextformetoedit.]}，T={a,b}，P如下:1.[q,Z,q]→b[q,X,q][q,Z,q]|ε2.[q,Z,q]→b[q,X,q][q1,Z,q]|ε3.[q,X,q]→bb[q,X,q]|ε4.[q,X,q]→b[q1,X,q]b5.[q1,Z,q]→a[q,Z,q]6.[q1,Z,q]→a[q1,Z,q]文法G產(chǎn)生的語言與下推自動機(jī)M接受的語言相同，即L(G)=L(M)。其中，產(chǎn)生式1和2對應(yīng)了M中的δ(q,b,Z)，產(chǎn)生式3和4對應(yīng)了M中的δ(q,b,X)和δ(q1,b,X)，產(chǎn)生式5和6對應(yīng)了M中的δ(q1,a,Z)。首先，刪除了一些格式錯誤的內(nèi)容和明顯有問題的段落，文章的意思變得更加清晰了。接下來，對每段話進(jìn)行了小幅度的改寫，使得表達(dá)更加流暢。1.給定一個文法G，其中S是起始符號，N是非終結(jié)符集合，T是終結(jié)符集合，P是產(chǎn)生式集合。我們可以通過使用算法1和算法2來消除無用符號，從而得到文法G的等價文法G'，使得G'只包含對于語言L(G)有意義的符號。2.對于給定的文法G，我們可以通過以下步驟來消除無用符號：(1)從起始符號S開始，使用深度優(yōu)先搜索算法找到所有能夠到達(dá)的非終結(jié)符號和終結(jié)符號。(2)從所有能夠到達(dá)的非終結(jié)符號開始，使用深度優(yōu)先搜索算法找到所有能夠推導(dǎo)出的非終結(jié)符號和終結(jié)符號。(3)刪去所有不能夠到達(dá)的非終結(jié)符號和無法推導(dǎo)出的產(chǎn)生式。3.對于給定的文法G，我們可以使用上述算法來消除無用符號，并得到一個等價文法G'。然后，我們可以使用以下步驟來判斷語言L(G)是否為上下文無關(guān)語言：(1)假設(shè)L(G)是上下文無關(guān)語言，則存在一個正整數(shù)p，使得對于每個字符串w∈L(G)，且|w|≥p，可以將w分解為uvwxy，其中|vx|≥1，|vwx|≤p，且uv^nwx^n∈L(G)，對于任意的n≥0。(2)對于給定的語言L(G)，我們可以構(gòu)造一個字符串w=anbncm，其中m≤n，且p的值大于等于n。根據(jù)上述假設(shè)，我們可以將w分解為uvwxy，其中|vx|≥1，|vwx|≤p，且uv^nwx^n∈L(G)，對于任意的n≥0。(3)考慮當(dāng)n=0時，我們有uv^0wx^0=ux^0?L(G)，因為m≠0。因此，假設(shè)不成立，即語言L(G)不是上下文無關(guān)語言。4.綜上所述，語言{anbncm|m≤n}不是上下文無關(guān)語言。iωω3iω4中會出現(xiàn)a,b,c的個數(shù)不再相等;這些與假設(shè)矛盾,故L不是上下文無關(guān)語言。改寫如下：證明：假設(shè)L是一個上下文無關(guān)語言。根據(jù)泵浦引理，我們可以取一個常數(shù)p，使得對于任何屬于L且長度大于等于p的字符串ω，都可以寫成ω=akbkck(k≥p)的形式，并且滿足|ω2ωω3|≤p。接下來，我們考慮以下三種情況：1.ω2和ω3不可能同時分別包含a和c，因為這樣會導(dǎo)致|ω2ωω3|>p。2.如果ω2和ω3都只包含a（或b或c），即ω2ωω3=aj(bj或cj)(j≤p)，那么當(dāng)i≠1時，ω1ω2iωω3iω4中會出現(xiàn)a、b、c的個數(shù)不再相等。3.如果ω2和ω3分別包含a和b（或b和c），那么ω1ω2iωω3iω4中會出現(xiàn)a、b、c的個數(shù)不再相等。由于以上三種情況與假設(shè)矛盾，故L不是上下文無關(guān)語言。.刪除明顯有問題的段落：無明顯問題的段落。2.小幅度改寫：3.在上下文無關(guān)語言中，有一個經(jīng)典的問題是判斷一個語言是否為上下文無關(guān)語言。對于某些語言，可以使用Chomsky范式文法來證明它是上下文無關(guān)語言。如果一個語言不是上下文無關(guān)語言，那么就需要找到一種方法來證明它不是上下文無關(guān)語言。常用的方法是假設(shè)該語言是上下文無關(guān)語言，并推出一些與假設(shè)矛盾的結(jié)論，從而證明該語言不是上下文無關(guān)語言。4.對于Chomsky范式文法，我們可以求出邊緣為ω的推導(dǎo)樹中最長路徑長度n與ω的長度|ω|之間的關(guān)系。設(shè)最長路徑長度為n，則|ω|≤2n-1。因為Chomsky范式文法的推導(dǎo)樹都是二叉樹，所以在最長路徑長度為n的二叉推導(dǎo)樹中，滿二叉樹推出的句子長度最長，為2n-1。因此，ω的長度與其推導(dǎo)樹的最長路徑長度n之間的關(guān)系可以用上式表示。25.設(shè)計一個PDA來接受語言{0m1n|m≤n}和{0m1n|m≥n}。對于第一個語言，我們可以設(shè)計PDAM=(Q,T,Г,δ,q,Z,F)，其中Q={q,q1,qf}，T={0,1}，Г={0,1,Z}，F(xiàn)={qf}，δ定義如下：δ(q,ε,Z)={(q1,Z)}δ(q,0,Z)={(q,0Z)}δ(q,0,0)={(q,00)}δ(q,1,Z)={(qf,ε)}δ(q,1,0)={(q1,ε)}δ(q1,1,0)={(q1,ε)}δ(q1,ε,Z)={(qf,ε)}δ(q1,1,Z)={(qf,ε)}δ(qf,1,ε)={(qf,ε)}對于第二個語言，我們可以設(shè)計PDAM=(Q,T,Г,δ,q,Z,F)，其中Q={q,q1,qf}，T={0,1}，Г={0,1,Z}，F(xiàn)={qf}，δ定義如下：δ(q,ε,Z)={(q1,Z)}δ(q,0,Z)={