《《形式語言與自動機(jī)》(王柏、楊娟編著)課后習(xí)題答案》由會員分享，可在線閱讀，更多相關(guān)《《形式語言與自動機(jī)》(王柏、楊娟編著)課后習(xí)題答案（15頁珍藏版）》請在裝配圖網(wǎng)上搜索。
1、形式語言與自動機(jī)課后習(xí)題答案
第二章
4．找出右線性文法，能構(gòu)成長度為1至5個字符且以字母為首的字符串。
答：G={N,T,P,S}
其中N={S,A,B,C,D} T={x,y} 其中x∈{所有字母} y∈{所有的字符} P如下:
S→x S→xA A→y A→yB
B→y B→yC C→y C→yD D→y
6．構(gòu)造上下文無關(guān)文法能夠產(chǎn)生
L={ω/ω∈{a,b}*且ω中a的個數(shù)是b的兩倍}
答：G={N,T,P,S}
其中N={S} T={a,b} P如下:
S→aab S→aba S→baa
S→aabS S→aaSb
2、 S→aSab S→Saab
S→abaS S→abSa S→aSba S→Saba
S→baaS S→baSa S→bSaa S→Sbaa
7．找出由下列各組生成式產(chǎn)生的語言（起始符為S）
(1) S→SaS S→b
(2) S→aSb S→c
(3) S→a S→aE E→aS
答：（1）b(ab)n /n≥0}或者L={(ba)nb /n≥0}
(2) L={ancbn /n≥0}
(3) L={a2n+1 /n≥0}
第三章
1． 下列集合是否為正則集，若是正則集寫出其正則式。
（1） 含有偶數(shù)個a和奇數(shù)個b的{a,b}*上的字符
3、串集合
（2） 含有相同個數(shù)a和b的字符串集合
（3） 不含子串a(chǎn)ba的{a,b}*上的字符串集合
答：（1）是正則集，自動機(jī)如下
奇a偶b
偶a偶b
a
a
b b b b
奇a奇b
偶a奇b
a
a
(2) 不是正則集，用泵浦引理可以證明，具體見17題（2）。
(
4、3) 是正則集
先看L’為包含子串a(chǎn)ba的{a,b}*上的字符串集合
顯然這是正則集，可以寫出表達(dá)式和畫出自動機(jī)。（略）
則不包含子串a(chǎn)ba的{a,b}*上的字符串集合L是L’的非。
根據(jù)正則集的性質(zhì)，L也是正則集。
4．對下列文法的生成式，找出其正則式
（1） G=({S,A,B,C,D},{a,b,c,d},P,S),生成式P如下：
S→aA S→B
A→abS A→bB
B→b B→cC
C→D D→bB
D→d
（2） G=({S,A,B,C,D},{a,b,c,d},P,S),生成式P如下：
S→aA S→B
A→cC A→bB
B
5、→bB B→a
C→D C→abB
D→d
答：(1) 由生成式得：
S=aA+B ①
A=abS+bB ②
B=b+cC ③
C=D ④
D=d+bB ⑤
③④⑤式化簡消去CD，得到B=b+c(d+bB)
即B=cbB+cd+b =>B=(cb)*(cd+b) ⑥
將②⑥代入①
S=aabS+ab(cb)*(cd+b)+(cb)*(cd+b) =>S=(aab)*(ab+ε)(cb)*(cd+b)
(2) 由生成式得：
S=aA+B ①
A=bB+cC ②
B=a+bB ③
C=D+abB ④
D=dB ⑤
由③得 B=b*a ⑥
將⑤⑥代
6、入④ C=d+abb*a=d+ab+a ⑦
將⑥⑦代入② A=b+a+c(d+b+a) ⑧
將⑥⑧代入① S=a(b+a+c(d+ab+a))+b*a
=ab+a+acd+acab+a+b*a
5.為下列正則集，構(gòu)造右線性文法：
(1){a,b}*
(2)以abb結(jié)尾的由a和b組成的所有字符串的集合
(3)以b為首后跟若干個a的字符串的集合
(4) 含有兩個相繼a和兩個相繼b的由a和b組成的所有字符串集合
答：（1）右線性文法G=({S},{a,b},P,S)
P: S→aS S→bS S→ε
(2) 右線性文法G=({S},{a,b},P,S)
7、
P: S→aS S→bS S→abb
(3) 此正則集為{ba*}
右線性文法G=({S,A},{a,b},P,S)
P: S→bA A→aA A→ε
(4) 此正則集為{{a,b}*aa{a,b}*bb{a,b}*, {a,b}*bb{a,b}*aa{a,b}*}
右線性文法G=({S,A,B,C},{a,b},P,S)
P: S→aS/bS/aaA/bbB
A→aA/bA/bbC
B→aB/bB/aaC
C→aC/bC/ε
7.設(shè)正則集為a(ba)*
(1) 構(gòu)造右線性文法
(2) 找出（1）中文法的有限自 b動機(jī)
答：（
8、1）右線性文法G=({S,A},{a,b},P,S)
P: S→aA A→bS A→ε
（2）自動機(jī)如下：
P2
P1
a
b
(p2是終結(jié)狀態(tài))
9.對應(yīng)圖（a）(b)的狀態(tài)轉(zhuǎn)換圖寫出正則式。（圖略）
（1） 由圖可知q0=aq0+bq1+a+ε
q1=aq2+bq1
q0=aq0+bq1+a
=>q1=abq1+bq1+aaq0+aa
=(b+ab) q1+aaq0+aa
=(b+ab) *( aaq0+aa)
=>q0=aq0+b(b+ab) *( aaq0+aa ) +a+ε
= q0(a
9、+b (b+ab) *aa)+ b(b+ab) *aa+a+ε
=(a+b (b+ab) *aa) *((b+ab) *aa+a+ε)
=(a+b (b+ab) *aa) *
(3) q0=aq1+bq2+a+b
q1=aq0+bq2+b
q0=aq1+bq0+a
=>q1=aq0+baq1+bbq0+ba+b
=(ba)*(aq0 +bbq0+ba+b)
=>q2=aaq0+abq2+bq0+ab+a
=(ab)*(aaq0 +bq0+ ab+a)
=>q0=a(ba)*(a+bb) q0 + a(ba)*(ba+b)+b(ab)*(aa+b)q0+ b(ab)*(ab
10、+a)+a+b
=[a(ba)*(a+bb) +b(ab)*(aa+b)]* (a(ba)*(ba+b)+ b(ab)*(ab+a)+a+b)
10.設(shè)字母表T={a,b},找出接受下列語言的DFA：
（1） 含有3個連續(xù)b的所有字符串集合
（2） 以aa為首的所有字符串集合
（3） 以aa結(jié)尾的所有字符串集合
答：（1）M=({q0,q1 q2,q3},{a,b},σ,q0,{q3}),其中σ如下：
a
b
q0
q0
q1
q1
q0
q2
q2
q0
q3
q3
q3
q3
（2）M=({q0,q1 q2 },{a,b},σ,q0,
11、{q2}),其中σ如下：
a
b
q0
q1
Φ
q1
q2
Φ
q2
q2
q2
（3）M=({q0,q1 q2 },{a,b},σ,q0,{q2}),其中σ如下：
a
b
q0
q1
q0
q1
q2
q0
q2
q2
q0
14構(gòu)造DFA M1等價于NFA M，NFA M如下：
（1）M=({q0,q1 q2,q3},{a,b},σ,q0,{q3}),其中σ如下：
σ(q0,a)={q0,q1} σ(q0,b)={q0}
σ(q1,a)={q2} σ(q1,b)= {q2 }
σ(q2,a)={q3}
12、 σ(q2,b)= Φ
σ(q3,a)={q3} σ(q3,b)= {q3 }
（2）M=({q0,q1 q2,q3},{a,b},σ,q0,{ q1,q2}),其中σ如下：
σ(q0,a)={q1,q2} σ(q0,b)={q1}
σ(q1,a)={q2} σ(q1,b)= {q1,q2 }
σ(q2,a)={q3} σ(q2,b)= {q0}
σ(q3,a)= Φσ(q3,b)= {q0}
答：（1）DFA M1={Q1, {a,b},σ1, [q0],{ [q0,q1,q3]，[q0,q2,q3]，[q0, q1,q2,q3]}
其中Q1 ={[q0],[
13、q0,q1], [q0,q1,q2],[ q0,q2],[ q0,q1, q2,q3],[ q0,q1, q3],[ q0,q2, q3],[ q0,q3]}
σ1滿足
a
b
[q0]
[q0,q1]
[ q0]
[q0,q1]
[q0,q1,q2]
[ q0,q2]
[q0,q1,q2]
[ q0,q1, q2,q3]
[ q0,q2]
[ q0,q2]
[ q0,q1, q3]
[q0]
[ q0,q1, q2,q3]
[ q0,q1, q2,q3]
[ q0,q2, q3]
[ q0,q1, q3]
[ q0,q1, q2,q3]
[ q0
14、,q2, q3]
[ q0,q2, q3]
[ q0,q1, q3]
[ q0,q3]
[ q0,q3]
[ q0,q1, q3]
[ q0,q3]
（2）DFA M1={Q1, {a,b},σ1, [q0],{ [q1],[q3], [q1,q3],[q0,q1,q2],[q1,q2] ,[q1,q2,q3],[q2,q3]}
其中Q1 ={[q0],[q1,q3], [q1],[q2],[ q0,q1,q2],[q1,q2],[q3], [q1,q2,q3],[q2,q3]}
σ1滿足
a
b
[q0]
[q1,q3]
[q1]
[q1,q3]
[
15、q2]
[ q0,q1,q2]
[q1]
[q2]
[q1,q2]
[q2]
[q3]
[q0]
[ q0,q1,q2]
[q1,q2,q3]
[ q0,q1,q2]
[q1,q2]
[q2,q3]
[ q0,q1,q2]
[q3]
Φ
[q0]
[q1,q2,q3]
[q2,q3]
[ q0,q1,q2]
[q2,q3]
[q3]
[q0]
15. 15.對下面矩陣表示的ε-NFA
ε
a
b
c
P(起始狀態(tài))
φ
{p}
{q}
{r}
q
{p}
{q}
{r}
φ
r(終止?fàn)顟B(tài))
{q}
{r}
16、
φ
{p}
(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},σ,p,r) 其中σ如表格所示。
因為ε-closure(p)= Φ
則設(shè)不含ε的NFA M1=({p,q,r},{a,b,c},σ1,p,r)
σ1(p,
17、a)=σ’(p,a)=ε-closure(σ(σ’(p,ε),a))={p}
σ1(p,b)=σ’(p,b)=ε-closure(σ(σ’(p,ε),b))={p,q}
σ1(p,c)=σ’(p,c)=ε-closure(σ(σ’(p,ε),c))={p,q,r}
σ1(q,a)=σ’(q,a)=ε-closure(σ(σ’(q,ε),a))={p,q}
σ1(q,b)=σ’(q,b)=ε-closure(σ(σ’(q,ε),b))={p,q,r}
σ1(q,c)=σ’(q,c)=ε-closure(σ(σ’(q,ε),c))={p,q,r}
σ1(r,a)=σ’(r,a)=ε-c
18、losure(σ(σ’(r,ε),a))={p,q,r}
σ1(r,b)=σ’(r,b)=ε-closure(σ(σ’(r,ε),b))={p,q,r}
σ1(r,c)=σ’(r,c)=ε-closure(σ(σ’(r,ε),c))={p,q,r}
圖示如下：(r為終止?fàn)顟B(tài))
p
q
b,c
a,b,c a,b,c a,b,c
c a,b,c b,c a,b,c
r
19、 a,b,c
16．設(shè)NFA M=({q0,q1},{a,b},σ,q0,{q1}),其中σ如下：
σ(q0,a)={q0,q1} σ(q0,b)={q1}
σ(q1,a)= Φ σ(q1,b)= {q0, q1}
構(gòu)造相應(yīng)的DFA M1，并進(jìn)行化簡
答：構(gòu)造一個相應(yīng)的DFA M1={Q1, {a,b},σ1, [q0],{ [q1]，[q0,q1]}
其中Q1 ={[q0]，[q1]，[q0,q1]}
σ1滿足
a
b
[q0]
[q0,q1]
[q1]
[q1]
Φ
[q0,q1]
[q0,
20、q1]
[q0,q1]
[q0,q1]
由于該DFA已是最簡，故不用化簡
17.使用泵浦引理，證明下列集合不是正則集：
（1） 由文法G的生成式S→aSbS/c產(chǎn)生的語言L(G)
（2） {ω/ω∈{a,b}*且ω有相同個數(shù)的a和b}
（3） {akcak/k≥1}
（4） {ωω/ω∈{a,b}*}
證明：（1）在L(G)中，a的個數(shù)與b的個數(shù)相等
假設(shè)L(G)是正則集，對于足夠大的k取ω= ak (cb)kc
令ω=ω1ω0ω2
因為|ω0|>0 |ω1ω0|≤k 存在ω0使ω1ω0iω2∈L
所以對于任意ω0只能取ω0=an n∈(0,k)
則ω1ω0iω
21、2= ak–n(an)i(cb)kc 在i不等于0時不屬于L
與假設(shè)矛盾。則L(G)不是正則集
（2）假設(shè)該集合是正則集，對于足夠大的k取ω= ak bk
令ω=ω1ω0ω2
因為|ω0|>0 |ω1ω0|≤k 存在ω0使ω1ω0iω2∈L
所以對于任意ω0只能取ω0=an n∈(0,k)
則ω1ω0iω2= ak–n(an)ibk 在i不等于0時a與b的個數(shù)不同，不屬于該集合
與假設(shè)矛盾。則該集合不是正則集
（3）假設(shè)該集合是正則集，對于足夠大的k取ω= ak cak
令ω=ω1ω0ω2
因為|ω0|>0 |ω1ω0|≤k 存在ω0使ω1ω0iω2∈L
所以對于任意ω
22、0只能取ω0=an n∈(0,k)
則ω1ω0iω2= ak–n(an)icak 在i不等于0時c前后a的個數(shù)不同，不屬于該集合
與假設(shè)矛盾。則該集合不是正則集
（4）假設(shè)該集合是正則集，對于足夠大的k取ωω= ak bakb
令ωω=ω1ω0ω2
因為|ω0|>0 |ω1ω0|≤k 存在ω0使ω1ω0iω2∈L
所以對于任意ω0只能取ω0=an n∈(0,k)
則ω1ω0iω2= ak–n(an)ibakb 在i不等于0時不滿足ωω的形式，不屬于該集合
與假設(shè)矛盾。則該集合不是正則集
18．構(gòu)造米蘭機(jī)和摩爾機(jī)
對于{a,b}*的字符串，如果輸入以bab結(jié)尾，則輸出
23、1；如果輸入以bba結(jié)尾，則輸出2；否則輸出3。
答：米蘭機(jī)：
說明狀態(tài)qaa表示到這個狀態(tài)時，輸入的字符串是以aa結(jié)尾。其他同理。
a/3
qaa
qab
b/3
a/3 a/3 b/3
b/1
qba
qbb
a/2 b/3
摩爾機(jī)，狀態(tài)說明同米蘭機(jī)。
a a
qaba,3 b/3
qa
24、ab,3 b/3
qaa,3 b/3
b a
a b a b
qbab,1 b/3
qbb,3 b/3
qbba,2 b/3
a b
25、 b
b
? 第四章
10. 把下列文法變換為無ε生成式、無單生成式和沒有無用符號的等價文法：
S →A1 | A2 , A1 →A3 | A4 , A2 →A4 | A5 , A3 →S | b |ε, A4 →S | a，A5 →S | d |ε
解: ⑴ 由算法3，變換為無ε生成式：
N’ = { S, A1,A2,A3,A4,A5 }
G1 = ( { S1,S, A1,A2,A3,A4,A5 } , { a,b,d }, P1 , S1 ) ,其中生成式P1如下：
S1 →ε| S
26、,
S →A1 | A2 ,
A1 →A3 | A4 ,
A2 →A4 | A5 ,
A3 →S | b ,
A4 →S | a ,
A5 →S | d ,
⑵ 由算法4，消單生成式：
NS1 = { S1,S,A1,A2,A3,A4, A5 } ,
NS = NA1 = NA2 = NA3 = NA4 = NA5 = { S, A1,A2,A3,A4, A5 } ,
運(yùn)用算法4，則P1變?yōu)椋?
S1 →a | b | d |ε ,
S →a | b | d ,
A1 →a | b | d ,
A2 →a | b | d ,
A3 →a | b | d ,
A4
27、→a | b | d ,
A5 →a | b | d
⑶ 由算法1和算法2，消除無用符號，得到符合題目要求的等價文法：
G1 = ( { S1 } , { a,b,d } , P1 , S1 ) ，其中生成式P1為：S1 →a | b | d |ε.
11. 設(shè)2型文法G = ( { S,A,B,C,D,E,F } , { a,b,c } , P , S ) , 其中P：
S →ASB |ε; A →aAS | a ; B →SBS | A | bb
試將G變換為無ε生成式,無單生成式,沒有無用符號的文法,再將其轉(zhuǎn)換為Chomsky范式.
解: ⑴ 由算法3，變換為無ε生成式
28、：
N’ = { S }
由S →ASB得出S →ASB | AB ,
由A →aAS得出A →aAS | aA ,
由B →SBS得出B →SBS | SB | BS |B,
由S∈N’ 得出S1 →ε| S ,
因此無ε的等效文法G1 = ( { S1,S,A,B } , { a,b,d } , P1 , S1 ) ,其中生成式P1如下：
S1 →ε| S ,
S →ASB | AB ,
A →aAS | aA | a,
B →SBS | SB | BS | B| A | bb ,
⑵ 由算法4，消單生成式：
NS1 = { S1,S } , NS = { S }
29、, NA = { A } , NB = { A,B }
由于S →ASB | AB∈P且不是單生成式,故P1中有S1 →ε| ASB | AB ,
同理有 S →ASB | AB , A →aAS | aA | a , B →SBS | SB | BS | aAS | aA | a | bb,
因此生成的無單生成式等效文法為
G1 = ( { S1,S, A,B } , { a,b } , P1 , S1 ) ,其中生成式P1如下：
S1 →ε| ASB | AB ,
S →ASB | AB ,
A →aAS | aA | a ,
B →SBS | SB | BS | aA
30、S | aA | a | bb,
⑶ 由算法1和算法2，消除無用符號(此題沒有無用符號);
⑷ 轉(zhuǎn)化為等價的Chomsky范式的文法:
將S1 →ASB變換為 S →AC , C →SB ,
將S →ASB 變換為 S →AC ,
將A →aAS | aA 變換為 A →ED | EA, D →AS , E →a,
將B →SBS | aAS | aA | a | bb , 變換為 B →CS | ED | EA | FF, F →b ,
⑸ 由此得出符合題目要求的等價文法：
G1 = ( { S1,S, A,B,C,D } , { a,b } , P1 , S1 ) ,其中生
31、成式P1如下：
S1 →ε| AC | AB ,
S →AC | AB ,
A →ED | EA | a ,
B →CS | SB | BS | ED | EA | a | FF ,
C →SB ,
D →AS ,
E →a ,
F →b .
15. 將下列文法變換為等價的Greibach范式文法:
⑴ S →DD | a , D →SS | b
解: 將非終結(jié)符排序為S,D,S為低位,D為高位,
⑴ 對于D →SS ,用S →DD | a 代入得 D →DDS | aS | b ,
用引理4.2.4,變化為D →aS | b | aSD' | bD' ,
32、D’ →DS | DSD’ ,
⑵ 將D生成式代入S生成式得 S →aSD | bD | aSD’D | bD'D | a ,
⑶ 將D生成式代入D’生成式得
D’ →aSS | bS | aSD'S | bD'S | aSS D' | bS D' | aSD'S D' | bD'S D' ,
⑷ 由此得出等價的Greibach范式文法：
G1 = ( { S,D,D’ } , { a,b } , P1 , S ) ,其中生成式P1如下：
S →aSD | bD | aSD’D | bD'D | a ,
D →aS | b | aSD' | bD' ,
D’ →aSS | bS
33、 | aSD'S | bD'S | aSS D' | bS D' | aSD'S D' | bD'S D' .
⑵ A1 →A3b | A2a , A2 →A1b | A2A2a | b , A3 →A1a | A3A3b | a
解: ⑴ 轉(zhuǎn)化為等價的Chomsky范式的文法:
A1 →A3A4 | A2A5 ,
A2 →A1A4 | A2A6 | b ,
A3 →A1A5 | A3A7 | a ,
A4 →b ,
A5 →a ,
A6 →A2A5 ,
A7 →A3A4 ,
⑵ 轉(zhuǎn)化為等價的Greibach范式的文法:
將非終結(jié)符排序為A1, A2,A3,A4
34、,A5 ,A1為低位A5為高位,
①對于A2 →A1A4 ,用A1 →A3A4 | A2A5代入得A2 →A3A4A4 | A2 A5A4 | A2A6 | b ,
用引理4.2.4,變化為
A2 →A3A4A4 | b | A3A4A4A2’ | bA2’ ,
A2’ →A5A4A2’ | A6A2’ | A5A4 | A6 ,
②對于A3 →A1A5 ,用A1 →A3A4 | A2A5代入得A3 →A3A4A5 | A2A5A5 | A3A7 | a ,
A3生成式右邊第一個字符仍是較低位的非終結(jié)符,將A2生成式代入A3生成式得
A3 →A3A4 A5 | A3A4A4 A5
35、A5 | b A5A5 | A3A4A4A2’ A5A5 | bA2’A5A5 | A3A7 | a ,
用引理4.2.4,變化為
A3 →b A5A5 | bA2’A5A5 | a | b A5A5A3’ | bA2’A5A5A3’ | aA3’ ,
A3’ →A4A5 | A4A4A5A5 | A4A4A2’A5A5 | A7 | A4A5A3’ | A4A4A5A5A3’ | A4A4A2’A5A5A3’ | A7A3’ ,
③對于A6 →A2A5 ,將A2生成式代入A6生成式得
A6 →A3A4A4A5 | bA5 | A3A4A4A2’A5 | bA2’A5 ,
A6生成
36、式右邊第一個字符仍是較低位的非終結(jié)符,將A3生成式代入A6生成式得
A6 →bA5A5A4A4A5 | bA2’A5A5A4A4A5 | aA4A4A5 | bA5A5A3’A4A4A5 | bA2’A5A5A3’A4A4A5 | aA3’A4A4A5 | bA5A5A4A4A2’A5 | bA2’A5A5A4A4A2’A5 | aA4A4A2’A5 | bA5A5A3’A4A4A2’A5 | bA2’A5A5A3’A4A4A2’A5 | aA3’A4A4A2’A5 | bA2’A5 | b A5 ,
④對于A7 →A3A4 , 將A3生成式代入A7生成式得
A7 →b A5A5A4 |
37、 bA2’A5A5A4 | a A4 | b A5A5A3’A4 | bA2’A5A5A3’A4 | aA3’A4 ,
⑤將A5,A6生成式代入A2’生成式得
A2’ →aA4A2’ | bA5A5A4A4A5A2’ | bA2’A5A5A4A4A5A2’ | aA4A4A5A2’ | bA5A5A3’A4A4A5A2’ | bA2’A5A5A3’A4A4A5A2’ | aA3’A4A4A5A2’ | bA5A5A4A4A2’A5 A2’ | bA2’A5A5A4A4A2’A5A2’ | aA4A4A2’A5A2’ | bA5A5A3’A4A4A2’A5A2’ | bA2’A5A5A3’A
38、4A4A2’A5A2’ | aA3’A4A4A2’A5A2’ | bA2’A5A2’ | b A5A2’ | aA4 | b A5A5A4A4A5 | bA2’A5A5A4A4A5 | aA4A4A5 | bA5A5A3’A4A4A5 | bA2’A5A5A3’A4A4A5 | aA3’A4A4A5 | bA5A5A4A4A2’A5 | bA2’A5A5A4A4A2’A5 | aA4A4A2’A5 | bA5A5A3’A4A4A2’A5 | bA2’A5A5A3’A4A4A2’A5 | aA3’A4A4A2’A5 | bA2’A5 | b A5 ,
將A4,A7生成式代入A3’生成式得
A
39、3’ →aA5 | aA4A5A5 | aA4A2’A5A5 | aA5A3’ | aA4A5A5A3’ | aA4A2’A5A5A3’ | b A5A5A4 | bA2’A5A5A4 | aA4 | bA5A5A3’A4 | bA2’A5A5A3’A4 | aA3’A4 | bA5A5A4A3’ | bA2’A5A5A4A3’ | a A4A3’ | b A5A5A3’A4 A3’ | bA2’A5A5A3’A4 A3’ | aA3’A4A3’ ,
⑶ 由此得出等價的Greibach范式文法:
G1 = ( { S,D,D’ } , { a,b } , P1 , S ) ,其中生成式P1
40、如下：
A1 →A3A4 | A2A5 ,
A2 →A3A4A4 | b | A3A4A4A2’ | bA2’ ,
A3 →b A5A5 | bA2’A5A5 | a | bA5A5A3’ | bA2’A5A5A3’ | aA3’ ,
A4 →b ,
A5 →a ,
A6 →bA5A5A4A4A5 | bA2’A5A5A4A4A5 | aA4A4A5 | bA5A5A3’A4A4A5 | bA2’A5A5A3’A4A4A5 | aA3’A4A4A5 | bA5A5A4A4A2’A5 | bA2’A5A5A4A4A2’A5 | aA4A4A2’A5 | bA5A5A3’A4A4A2’
41、A5 | bA2’A5A5A3’A4A4A2’A5 | aA3’A4A4A2’A5 | bA2’A5 | b A5 ,
A7 →b A5A5A4 | bA2’A5A5A4 | a A4 | b A5A5A3’A4 | bA2’A5A5A3’A4 | aA3’A4 ,
A2’ →aA4A2’ | bA5A5A4A4A5A2’ | bA2’A5A5A4A4A5A2’ | aA4A4A5A2’ | bA5A5A3’A4A4A5A2’ | bA2’A5A5A3’A4A4A5A2’ | aA3’A4A4A5A2’ | bA5A5A4A4A2’A5 A2’ | bA2’A5A5A4A4A2’A5A2’
42、 | aA4A4A2’A5A2’ | bA5A5A3’A4A4A2’A5A2’ | bA2’A5A5A3’A4A4A2’A5A2’ | aA3’A4A4A2’A5A2’ | bA2’A5A2’ | bA5A2’ | aA4 | b A5A5A4A4A5 | bA2’A5A5A4A4A5 | aA4A4A5 | bA5A5A3’A4A4A5 | bA2’A5A5A3’A4A4A5 | aA3’A4A4A5 | bA5A5A4A4A2’A5 | bA2’A5A5A4A4A2’A5 | aA4A4A2’A5 | bA5A5A3’A4A4A2’A5 | bA2’A5A5A3’A4A4A2’A5 | a
43、A3’A4A4A2’A5 | bA2’A5 | b A5 ,
A3’ →aA5 | aA4A5A5 | aA4A2’A5A5 | aA5A3’ | aA4A5A5A3’ | aA4A2’A5A5A3’ | b A5A5A4 | bA2’A5A5A4 | aA4 | bA5A5A3’A4 | bA2’A5A5A3’A4 | aA3’A4 | bA5A5A4A3’ | bA2’A5A5A4A3’ | a A4 A3’ | b A5A5A3’A4 A3’ | bA2’A5A5A3’A4 A3’ | aA3’A4A3’ .
20. 設(shè)文法G有如下得生成式: S →aDD , D →aS | b
44、S | a , 構(gòu)造等價的下推自動機(jī).
解: 根據(jù)P162-163的算法,構(gòu)造下推自動機(jī)M,使M按文法G的最左推導(dǎo)方式工作.
設(shè)M = (Q,T,Г,δ,q0,Z0,F ),其中
Q = { q0,qf } ,
T = { a,b} ,
Г = { a,b,D,S } ,
Z0 = S ,
F = { qf } ,
δ定義如下:
δ( q0,ε,S ) = { ( q0, aDD ) } ,
δ( q0,ε,D ) = { ( q0,aS ) , ( q0,bS ) , ( q0,a ) } ,
δ( q0,a,a ) = { ( q0,ε ) } ,
δ( q0,
45、ε,ε ) = { ( qf,ε ) } .
21. 給出產(chǎn)生語言 L = { aibjck | i , j , k≥0 且 i = j 或者 j = k }的上下文無關(guān)文法.你給出的文法是否具有二義性?為什么?
解: G=({S,A,B,C,D,E},{a,b,c}，P，S)
P：S →AD |EB, A →aAb |ε, B →bBc |ε, D →cD |ε, E →aE |ε
文法具有二義性。
因為當(dāng)句子ω中a,b,c個數(shù)相同時，對于ω存在兩個不同的最左(右)推導(dǎo)。
如abc?L，存在兩個不同的最左推導(dǎo) STADTaAbDTabDTabcCTabc 及STEBTaEBT
46、aBTabBcTabc 。
22. 設(shè)下推自動機(jī) M = ( {q0,q1},{a,b},{Z0,X},δ, q0, Z0,φ),其中δ如下:
δ(q0,b, Z0) = {(q0, XZ0)} ,δ(q0,ε, Z0) = {(q0, ε)} ,A
δ(q0,b, X) = {(q0, XX)} , δ(q1,b, X) = {(q1, ε)} ,
δ(q0,b, X) = {(q1, X)} , δ(q1,a, Z0) = {(q0, Z0)} ,
試構(gòu)造文法G產(chǎn)生的語言 L (G) = L(M).
解: 在G中,N = { [q0,Z0,q0], [q0,Z0,q1]
47、, [q0,X,q0], [q0,X,q1], [q1,Z0,q0], [q1,Z0,q1], [q1,X,q0], [q1,X,q1] } .
⑴ S生成式有
S →[q0,Z0,q0] ,
S →[q0,Z0,q1] ,
根據(jù)δ(q0,b, Z0) = {(q0, XZ0)} ,則有
[q0,Z0,q0] →b[q0,X,q0] [q0,Z0,q0] ,
[q0,Z0,q0] →b[q0,X,q1] [q1,Z0,q0] ,
[q0,Z0,q1] →b[q0,X,q0] [q0,Z0,q1] ,
[q0,Z0,q1] →b[q0,X,q1] [q1,Z0,q1] ,
48、 因為有δ(q0,b, X) = {(q0, XX)},則有
[q0,X,q0] →b[q0,X,q0] [q0,X,q0] ,
[q0, X,q0] →b[q0,X,q1] [q1, X,q0] ,
[q0, X,q1] →b[q0,X,q0] [q0, X,q1] ,
[q0, X,q1] →b[q0,X,q1] [q1, X,q1] ,
因為有δ(q0,a, X) = {(q1, X)},則有
[q0,X,q0] →a[q1,X,q0] ,
[q0,X,q1] →a[q1,X,q1] ,
因為有δ(q1,a, Z0) = {(q0, Z0)},則有
[q1,Z0,q
49、0] →a[q0,Z0,q0] ,
[q1,Z0,q1] →a[q0,Z0,q1] ,
因為有δ(q0,ε, Z0) = {(q0, ε)},則有
[q0,Z0,q0] →ε,
因為有δ(q1,b, X) = {(q1, ε)},則有
[q1,X,q1] →ε
⑵ 利用算法1和算法2,消除無用符號后,得出文法G產(chǎn)生的語言L(G) = { N,T,P,S }
其中N = { S,[q0,Z0,q0],[q1,Z0,q0],[q1,X,q1], [q0,X,q1] },T = { a,b },生成式P如下:
S →[q0,Z0,q0] ,
[q0,Z0,q0] →b[q0
50、,X,q1] [q1,Z0,q0] ,
[q0, X,q1] →b[q0,X,q1] [q1, X,q1] ,
[q0,X,q1] →a[q1,X,q1] ,
[q1,Z0,q0] →a[q0,Z0,q0] ,
[q0,Z0,q0] →ε,
[q0,Z0,q0] →ε.
23. 證明下列語言不是上下文無關(guān)語言:
⑴ { anbncm | m≤n };
證明: 假設(shè)L是上下文無關(guān)語言,由泵浦引理,取常數(shù)p,當(dāng)ω∈L且|ω|≥p時,可取
ω = apbpcp ,將ω寫為ω=ω1ω2ω0ω3ω4 ,同時滿足|ω2ω0ω3|≤p
⑴ ω2和ω3不可能同時分別包含a和c,因為在這
51、種情況下,有|ω2ω0ω3|>p;
⑵ 如果ω2和ω3都只包含a (b) ,即ω2ω0ω3 = aj (bj ) (j≤p) ,則當(dāng)i≠1時, ω1ω2iω0ω3iω4中會出現(xiàn)a的個數(shù)與b的個數(shù)不等;
如果ω2和ω3都只包含c ,即ω2ω0ω3 = cj (j≤p),當(dāng)i大于1時,ω1ω2iω0ω3iω4中會出現(xiàn)c的個數(shù)大于a的個數(shù) (b的個數(shù));
⑶ 如果ω2和ω3分別包含a和b (b和c) ,當(dāng)i=0時 ω1ω2iω0ω3iω4中會出現(xiàn)a, b的個數(shù)小于c的個數(shù)（或a,b個數(shù)不等）
這些與假設(shè)矛盾,故L不是上下文無關(guān)語言.
⑵ { ak | k是質(zhì)數(shù) };
證明: 假設(shè)L是上
52、下文無關(guān)語言,由泵浦引理,取常數(shù)p,當(dāng)ω∈L且|ω|≥p時,可取ω=ak ( k≥p且k≠1 ) ,將ω寫為ω=ω1ω2ω0ω3ω4 ,同時滿足|ω2ω0ω3|≤p ,且
|ω2ω3|=j≥1 ,則當(dāng)i=k+1時,|ω1ω2iω0ω3iω4|=k+(i-1)*j=k+k*j= k*(1+j) ,k*(1+j)至少包含因子k且k≠1 ,因此必定不是質(zhì)數(shù),即ω1ω2iω0ω3iω4不屬于L.
這與假設(shè)矛盾,故L不是上下文無關(guān)語言.
⑶ 由 a,b,c 組成的字符串且是含有 a,b,c 的個數(shù)相同的所有字符串.
證明: 假設(shè)L是上下文無關(guān)語言,由泵浦引理,取常數(shù)p,當(dāng)ω∈L且|ω|≥p
53、時,可取
ω = akbkck (k≥p) ,將ω寫為ω=ω1ω2ω0ω3ω4 ,同時滿足|ω2ω0ω3|≤p
⑴ ω2和ω3不可能同時分別包含a和c,因為在這種情況下,有|ω2ω0ω3|>p;
⑵ 如果ω2和ω3都只包含a (b或c) ,即ω2ω0ω3 = aj (bj或cj ) (j≤p) ,則當(dāng)i≠1時, ω1ω2iω0ω3iω4中會出現(xiàn)a,b,c的個數(shù)不再相等;
⑶ 如果ω2和ω3分別包含a和b (b和c) , ω1ω2iω0ω3iω4中會出現(xiàn)a,b的個數(shù)與c的不等;
這些與假設(shè)矛盾,故L不是上下文無關(guān)語言.
24. 設(shè)G是Chomsky 范式文法,存在ω∈ L (G
54、) ，求在邊緣為ω的推導(dǎo)樹中,最長的路徑長度與ω的長度之間的關(guān)系.
解: 設(shè)邊緣為ω的推導(dǎo)樹中,最長路徑長度為n,則它與ω的長度之間的關(guān)系為|ω|≤2n-1 .
因為由Chomsky范式的定義可知,Chomsky范式文法的推導(dǎo)樹都是二叉樹,在最長路徑長度為n的二叉推導(dǎo)樹中,滿二叉樹推出的句子長度最長,為2n-1,因此ω的長度與其推導(dǎo)樹的最長路徑長度n的關(guān)系可以用上式表示.
25. 設(shè)計PDA接受下列語言(注意:不要求為確定的)
⑴ { 0m1n | m≤n };
解: 設(shè)PDA M = ( Q,T,Г,δ,q0,Z0,F ),其中
Q = { q0,q1,qf } ,
T =
55、 { 0,1} ,
Г = { 0,1, Z0 } ,
F = { qf } ,
δ定義如下:
δ( q0, ε, Z0 ) = { ( q1, Z0 ) } ,
δ( q0,0, Z0 ) = { ( q0, 0Z0 ) } ,
δ( q0,0,0 ) = { ( q0, 00 ) } ,
δ( q0,1, Z0 ) = { ( qf,ε ) } ,
δ( q0,1, 0 ) = { ( q1,ε ) } ,
δ( q1,1, 0 ) = { ( q1,ε ) } ,
δ( q1,ε, Z0 ) = { ( qf,ε ) }
δ( q1,1, Z0 ) = { (
56、qf,ε ) }
δ( qf,1, ε) = { ( qf,ε ) }
⑵ { 0m1n | m≥n };
解: 設(shè)PDA M = ( Q,T,Г,δ,q0,Z0,F ),其中
Q = { q0,q1,qf } ,
T = { 0,1} ,
Г = { 0,1, Z0 } ,
F = { qf } ,
δ定義如下:
δ( q0, ε, Z0 ) = { ( q1, Z0 ) } ,
δ( q0,0, Z0 ) = { ( q0, 0Z0 ) } ,
δ( q0,0,0 ) = { ( q0, 00 ) } ,
δ( q0,1, 0 ) = { ( q1,ε ) }
57、 ,
δ( q1,1, 0 ) = { ( q1,ε ) } ,
δ( q1,ε,Z0 ) = { ( qf,ε ) } ,
δ( q1,ε,0 ) = { ( qf,ε ) }
δ( qf,1, ε) = { ( qf,ε ) }
⑶ { 0m1n0m | n和m任意 };
解: 設(shè)PDA M = ( Q,T,Г,δ,q0,Z0,F ),其中
Q = { q0,q1, q2,q3,qf } ,
T = { 0,1} ,
Г = { 0,1, Z0 } ,
F = { qf } ,
δ定義如下:
δ( q0,0, Z0 ) = { ( q0, 0Z0 ) } ,
58、δ( q0,0,0 ) = { ( q0, 00 ),( q0,ε)} ,
δ( q0,1, Z0 ) = { ( q3,ε ) } ,
δ( q3,1, ε) = { (q3,ε) } ,
δ( q3,ε, ε) = { ( qf,ε ) } ,
δ( q0,1,0 ) = { ( q1,0 ) } ,
δ( q1,1,0 ) = { ( q1,0 ) } ,
δ( q1,0,0 ) = { ( q2,ε ) } ,
δ( q2,0,0 ) = { ( q2,ε ) } ,
δ( q2,ε, Z0 ) = { ( qf,ε ) } ,
δ( q0, ε, Z0 ) = {
59、( qf, ε)}nm
? 第五章
1. 考慮如下的圖靈機(jī) M = ( {q0, q1, qf, },{0,1},{0,1,B},δ, q0,B,{ qf } ),其中δ定義為:
δ(q0,0) = {(q1,1,R)} , δ(q1,1) = {(q0,0,R)} , δ(q1,B) = {(qf,B,R)} ,
非形式化但準(zhǔn)確地描述該圖靈機(jī)的工作過程及其所接受的語言.
解: 開始時,M的帶上從左端起放有字符串0(10)i (i≥0),后跟無限多個空白符B.M的第一次動作先讀到第一個0,并改寫為1;然后右移,如果找到第一個1,則改寫為0,并繼續(xù)向右尋找下一個0,這樣重復(fù)進(jìn)行.當(dāng)向右尋找1的時候,找到一個空白符B,則結(jié)束.
該圖靈機(jī)所接受的語言L(M) = { 0(10)i | i≥
《形式語言與自動機(jī)》(王柏、楊娟編著)課后習(xí)題答案
