《北郵形式語言與自動機(jī)四五章答案.doc》由會員分享，可在線閱讀，更多相關(guān)《北郵形式語言與自動機(jī)四五章答案.doc（8頁珍藏版）》請?jiān)谘b配圖網(wǎng)上搜索。

1、形式語言與自動機(jī) 四、五章部分習(xí)題答案 形式語言與自動機(jī)作業(yè)參考答案（僅供參考） 第四章 2．最左推導(dǎo)：E→E+T→T+T→E+T→b+T→b+T/F→b+F/F→b+b/F→b+b/b 最右推導(dǎo)：E→E+T→E+T/F→E+T/b→E+F/b→E+b/b→T+b/b→F+b/b→b+b/b 8.(1)由題：S,D,E為有用非終結(jié)符，刪去有關(guān)C的生成式，得：G1:S→ED,D→a,E→b (2)由題：S,D,E為有用非終結(jié)符，刪去有關(guān)C的生成式，得：G2:S→D,D→b

2、S|b,E→DS|b. 又E不可達(dá)，刪去有關(guān)E得生成式，得：G2:S→D,D→bS|b 9．由題：N’={S,C,D,E},因?yàn)镾∈N’，所以P1中加入生成式:S1→S|ε,變換后的無ε生成式的等價(jià)文法為：G1={N1,T,P1,S1} N1={S1,S,C,D,E} P1:S1→S|ε S→DCE,D→CC,C→EE|b,E→DD|a 10. 把下列文法變換為無ε生成式、無單生成式和沒有無用符號的等價(jià)文法： S →A1 | A2 , A1 →A3 | A4 , A2 →A4 | A5 , A3 →S | b |ε, A4 →S | a，A5 →S | d |ε 解: ⑴ 由算法

3、3，變換為無ε生成式： N’ = { S, A1,A2,A3,A4,A5 } G1 = ( { S1,S, A1,A2,A3,A4,A5 } , { a,b,d }, P1 , S1 ) ,其中生成式P1如下： S1 →ε| S , 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,A

4、3,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 →a | b | d , A5 →a | b | d ⑶ 由算法1和算法2，消除無用符號，得到符合題目要求的等價(jià)文法： 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 ,

5、 S ) , 其中P： S →ASB |ε; A →aAS | a ; B →SBS | A | bb 試將G變換為無ε生成式,無單生成式,沒有無用符號的文法,再將其轉(zhuǎn)換為Chomsky范式. 解: ⑴ 由算法3，變換為無ε生成式： 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

6、 →ε| S , S →ASB | AB , A →aAS | aA | a, B →SBS | SB | BS | B| A | bb , ⑵ 由算法4，消單生成式： NS1 = { S1,S } , NS = { S } , 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,

7、 A,B } , { a,b } , P1 , S1 ) ,其中生成式P1如下： S1 →ε| ASB | AB , S →ASB | AB , A →aAS | aA | a , B →SBS | SB | BS | aAS | aA | a | bb, ⑶ 由算法1和算法2，消除無用符號(此題沒有無用符號); ⑷ 轉(zhuǎn)化為等價(jià)的Chomsky范式的文法: 將S1 →ASB變換為 S1 →AC , C →SB , 將S →ASB 變換為 S →AC , 將A →aAS | aA 變換為 A →ED | EA, D →AS , E →a, 將B →SBS | aAS |

8、aA | a | bb , 變換為 B →CS | ED | EA | FF, F →b , ⑸ 由此得出符合題目要求的等價(jià)文法： G1 = ( { S1,S, A,B,C,D } , { a,b } , P1 , S1 ) ,其中生成式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. 將下列文法變換為等價(jià)的Greibach范式文法: ⑴ S →DD | a , D

9、→SS | b 解: 將非終結(jié)符排序?yàn)镾,D,S為低位,D為高位, ⑴ 對于D →SS ,用S →DD | a 代入得 D →DDS | aS | b , 用引理4.2.4,變化為D →aS | b | aSD | bD , D’ →DS | DSD’ , ⑵ 將D生成式代入S生成式得 S →aSD | bD | aSD’D | bDD | a , ⑶ 將D生成式代入D’生成式得 D’ →aSS | bS | aSDS | bDS | aSS D | bS D | aSDS D | bDS D , ⑷ 由此得出等價(jià)的Greibach范式文法： G1 = ( { S,D,D’

10、} , { a,b } , P1 , S ) ,其中生成式P1如下： S →aSD | bD | aSD’D | bDD | a , D →aS | b | aSD | bD , D’ →aSS | bS | aSDS | bDS | aSS D | bS D | aSDS D | bDS D . ⑵ A1 →A3b | A2a , A2 →A1b | A2A2a | b , A3 →A1a | A3A3b | a 解: ⑴ 轉(zhuǎn)化為等價(jià)的Chomsky范式的文法: A1 →A3A4 | A2A5 , A2 →A1A4 | A2A6 | b , A3 →A1A5 | A

11、3A7 | a , A4 →b , A5 →a , A6 →A2A5 , A7 →A3A4 , ⑵ 轉(zhuǎn)化為等價(jià)的Greibach范式的文法: 將非終結(jié)符排序?yàn)锳1, A2,A3,A4,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代入

12、得A3 →A3A4A5 | A2A5A5 | A3A7 | a , A3生成式右邊第一個(gè)字符仍是較低位的非終結(jié)符,將A2生成式代入A3生成式得 A3 →A3A4 A5 | A3A4A4 A5A5 | 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’

13、A5A5A3’ | A7A3’ , ③對于A6 →A2A5 ,將A2生成式代入A6生成式得 A6 →A3A4A4A5 | bA5 | A3A4A4A2’A5 | bA2’A5 , A6生成式右邊第一個(gè)字符仍是較低位的非終結(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

14、’A5A5A3’A4A4A2’A5 | aA3’A4A4A2’A5 | bA2’A5 | b A5 , ④對于A7 →A3A4 , 將A3生成式代入A7生成式得 A7 →b A5A5A4 | 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’

15、| bA5A5A4A4A2’A5 A2’ | bA2’A5A5A4A4A2’A5A2’ | aA4A4A2’A5A2’ | bA5A5A3’A4A4A2’A5A2’ | bA2’A5A5A3’A4A4A2’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 |

16、bA5A5A3’A4A4A2’A5 | bA2’A5A5A3’A4A4A2’A5 | aA3’A4A4A2’A5 | bA2’A5 | b A5 , 將A4,A7生成式代入A3’生成式得 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 A4A3’ | b A5A5A3’A4 A3’ | bA2’A5A

17、5A3’A4 A3’ | aA3’A4A3’ , ⑶ 由此得出等價(jià)的Greibach范式文法: G1 = ( { S,D,D’ } , { a,b } , P1 , S ) ,其中生成式P1如下： 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 | b

18、A2’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 →b A5A5A4 | bA2’A5A5A4 | a A4 | b A5A5A3’A4 | bA2’A5A5A3’A4 | aA3’A4 , A2’ →aA4A2’ | bA5A5A4A4A5A2’ | bA2’A5A5A4A4A5A2’ | aA4A4A5A2’ | bA5

19、A5A3’A4A4A5A2’ | bA2’A5A5A3’A4A4A5A2’ | aA3’A4A4A5A2’ | bA5A5A4A4A2’A5 A2’ | bA2’A5A5A4A4A2’A5A2’ | 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

20、 | bA5A5A4A4A2’A5 | bA2’A5A5A4A4A2’A5 | aA4A4A2’A5 | bA5A5A3’A4A4A2’A5 | bA2’A5A5A3’A4A4A2’A5 | aA3’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

21、A4 A3’ | b A5A5A3’A4 A3’ | bA2’A5A5A3’A4 A3’ | aA3’A4A3’ . 20. 設(shè)文法G有如下得生成式: S →aDD , D →aS | bS | a , 構(gòu)造等價(jià)的下推自動機(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

22、) } , δ( q0,ε,D ) = { ( q0,aS ) , ( q0,bS ) , ( q0,a ) } , δ( q0,a,a ) = { ( q0,ε ) } , δ( q0,b,b ) = { ( q0,ε ) } , δ( q0,ε,ε ) = { ( 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 →b

23、Bc |ε, D →cD |ε, E →aE |ε 文法具有二義性。 因?yàn)楫?dāng)句子ω中a,b,c個(gè)數(shù)相同時(shí)，對于ω存在兩個(gè)不同的最左(右)推導(dǎo)。 如abcL，存在兩個(gè)不同的最左推導(dǎo) SADaAbDabDabcCabc 及SEBaEBaBabBcabc 。 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, ε)} , δ

24、(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], [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

25、] , [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] , 因?yàn)橛笑?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] , 因?yàn)橛笑?

26、q0,a, X) = {(q1, X)},則有 [q0,X,q0] →a[q1,X,q0] , [q0,X,q1] →a[q1,X,q1] , 因?yàn)橛笑?q1,a, Z0) = {(q0, Z0)},則有 [q1,Z0,q0] →a[q0,Z0,q0] , [q1,Z0,q1] →a[q0,Z0,q1] , 因?yàn)橛笑?q0,ε, Z0) = {(q0, ε)},則有 [q0,Z0,q0] →ε, 因?yàn)橛笑?q1,b, X) = {(q1, ε)},則有 [q1,X,q1] →ε ⑵ 利用算法1和算法2,消除無用符號后,得出文法G產(chǎn)生的語言L(G) = { N,T,P,

27、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,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 }

28、; 證明: 假設(shè)L是上下文無關(guān)語言,由泵浦引理,取常數(shù)p,當(dāng)ω∈L且|ω|≥p時(shí),可取 ω = apbpcp ,將ω寫為ω=ω1ω2ω0ω3ω4 ,同時(shí)滿足|ω2ω0ω3|≤p ⑴ ω2和ω3不可能同時(shí)分別包含a和c,因?yàn)樵谶@種情況下,有|ω2ω0ω3|>p; ⑵ 如果ω2和ω3都只包含a (b) ,即ω2ω0ω3 = aj (bj ) (j≤p) ,則當(dāng)i≠1時(shí), ω1ω2iω0ω3iω4中會出現(xiàn)a的個(gè)數(shù)與b的個(gè)數(shù)不等; 如果ω2和ω3都只包含c ,即ω2ω0ω3 = cj (j≤p),當(dāng)i大于1時(shí),ω1ω2iω0ω3iω4中會出現(xiàn)c的個(gè)數(shù)大于a的個(gè)數(shù) (b的個(gè)數(shù)); ⑶ 如果

29、ω2和ω3分別包含a和b (b和c) ,當(dāng)i=0時(shí) ω1ω2iω0ω3iω4中會出現(xiàn)a, b的個(gè)數(shù)小于c的個(gè)數(shù)（或a,b個(gè)數(shù)不等） 這些與假設(shè)矛盾,故L不是上下文無關(guān)語言. ⑵ { ak | k是質(zhì)數(shù) }; 證明: 假設(shè)L是上下文無關(guān)語言,由泵浦引理,取常數(shù)p,當(dāng)ω∈L且|ω|≥p時(shí),可取ω=ak ( k≥p且k≠1 ) ,將ω寫為ω=ω1ω2ω0ω3ω4 ,同時(shí)滿足|ω2ω0ω3|≤p ,且 |ω2ω3|=j≥1 ,則當(dāng)i=k+1時(shí),|ω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

30、ω0ω3iω4不屬于L. 這與假設(shè)矛盾,故L不是上下文無關(guān)語言. ⑶ 由 a,b,c 組成的字符串且是含有 a,b,c 的個(gè)數(shù)相同的所有字符串. 證明: 假設(shè)L是上下文無關(guān)語言,由泵浦引理,取常數(shù)p,當(dāng)ω∈L且|ω|≥p時(shí),可取 ω = akbkck (k≥p) ,將ω寫為ω=ω1ω2ω0ω3ω4 ,同時(shí)滿足|ω2ω0ω3|≤p ⑴ ω2和ω3不可能同時(shí)分別包含a和c,因?yàn)樵谶@種情況下,有|ω2ω0ω3|>p; ⑵ 如果ω2和ω3都只包含a (b或c) ,即ω2ω0ω3 = aj (bj或cj ) (j≤p) ,則當(dāng)i≠1時(shí), ω1ω2iω0ω3iω4中會出現(xiàn)a,b,c的個(gè)

31、數(shù)不再相等; ⑶ 如果ω2和ω3分別包含a和b (b和c) , ω1ω2iω0ω3iω4中會出現(xiàn)a,b的個(gè)數(shù)與c的不等; 這些與假設(shè)矛盾,故L不是上下文無關(guān)語言. 24. 設(shè)G是Chomsky 范式文法,存在ω∈ L (G) ，求在邊緣為ω的推導(dǎo)樹中,最長的路徑長度與ω的長度之間的關(guān)系. 解: 設(shè)邊緣為ω的推導(dǎo)樹中,最長路徑長度為n,則它與ω的長度之間的關(guān)系為|ω|≤2n-1 . 因?yàn)橛蒀homsky范式的定義可知,Chomsky范式文法的推導(dǎo)樹都是二叉樹,在最長路徑長度為n的二叉推導(dǎo)樹中,滿二叉樹推出的句子長度最長,為2n-1,因此ω的長度與其推導(dǎo)樹的最長路徑長度n的關(guān)系可以用

32、上式表示. 25. 設(shè)計(jì)PDA接受下列語言(注意:不要求為確定的) ⑴ { 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, Z0 ) = { ( qf,ε ) }

33、, δ( q0,1, 0 ) = { ( q1,ε ) } , δ( q1,1, 0 ) = { ( q1,ε ) } , δ( q1,ε, Z0 ) = { ( qf,ε ) } δ( q1,1, Z0 ) = { ( 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

34、) = { ( q1, Z0 ) } , δ( q0,0, Z0 ) = { ( q0, 0Z0 ) } , δ( q0,0,0 ) = { ( q0, 00 ) } , δ( q0,1, 0 ) = { ( q1,ε ) } , δ( 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

35、= { q0,q1, q2,q3,qf } , T = { 0,1} , Г = { 0,1, Z0 } , F = { qf } , δ定義如下: δ( q0,0, Z0 ) = { ( q0, 0Z0 ) } , δ( 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 )

36、} , δ( q1,0,0 ) = { ( q2,ε ) } , δ( q2,0,0 ) = { ( q2,ε ) } , δ( q2,ε, Z0 ) = { ( qf,ε ) } , δ( q0, ε, Z0 ) = { ( 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ī)的工作過程及其所接受的語言. 解: 開始時(shí),M的帶上從左端起放有字符串0(10)i (i≥0),后跟無限多個(gè)空白符B.M的第一次動作先讀到第一個(gè)0,并改寫為1;然后右移,如果找到第一個(gè)1,則改寫為0,并繼續(xù)向右尋找下一個(gè)0,這樣重復(fù)進(jìn)行.當(dāng)向右尋找1的時(shí)候,找到一個(gè)空白符B,則結(jié)束. 該圖靈機(jī)所接受的語言L(M) = { 0(10)i | i≥0 } . 8