形式語(yǔ)言與自動(dòng)機(jī)

1、形式語(yǔ)言與自動(dòng)機(jī)理論Formal Languages and Automata Theory朱保平朱保平南京理工大學(xué)計(jì)算機(jī)學(xué)院南京理工大學(xué)計(jì)算機(jī)學(xué)院形式語(yǔ)言形式語(yǔ)言形式語(yǔ)言 形式語(yǔ)言是研究自然語(yǔ)言和人工語(yǔ)言的數(shù)學(xué)工具，只研究組成規(guī)則，不研形式語(yǔ)言是研究自然語(yǔ)言和人工語(yǔ)言的數(shù)學(xué)工具，只研究組成規(guī)則，不研究語(yǔ)義。究語(yǔ)義。- 將語(yǔ)言看做句子的集合將語(yǔ)言看做句子的集合- 將句子看做字母按照一定規(guī)則組成的字符串將句子看做字母按照一定規(guī)則組成的字符串- 根據(jù)規(guī)則的形式區(qū)分語(yǔ)言類根據(jù)規(guī)則的形式區(qū)分語(yǔ)言類; ;- 大部分問(wèn)題都可轉(zhuǎn)化為判定某個(gè)句子是否屬于某個(gè)語(yǔ)言的問(wèn)題大部分問(wèn)題都可轉(zhuǎn)化為判定某個(gè)句子是否屬于某

2、個(gè)語(yǔ)言的問(wèn)題 發(fā)展過(guò)程發(fā)展過(guò)程克林克林(Kleene)在在1951-1956年間，在研究神經(jīng)細(xì)胞中建立了自動(dòng)機(jī)年間，在研究神經(jīng)細(xì)胞中建立了自動(dòng)機(jī)來(lái)識(shí)別語(yǔ)言。來(lái)識(shí)別語(yǔ)言。1956年，喬姆斯基年，喬姆斯基(Chomsky)從產(chǎn)生語(yǔ)言的角度研究語(yǔ)言。從產(chǎn)生語(yǔ)言的角度研究語(yǔ)言。L*，文法文法(grammar)。1959年，喬姆斯基證明了文法與自動(dòng)機(jī)的等價(jià)性。年，喬姆斯基證明了文法與自動(dòng)機(jī)的等價(jià)性。自動(dòng)機(jī)自動(dòng)機(jī)理論自動(dòng)機(jī)理論自動(dòng)機(jī)理論研究抽象計(jì)算裝置或自動(dòng)機(jī)理論研究抽象計(jì)算裝置或“機(jī)器機(jī)器”。 以狀態(tài)自動(dòng)機(jī)為基礎(chǔ)，建立抽象機(jī)器模型；以狀態(tài)自動(dòng)機(jī)為基礎(chǔ)，建立抽象機(jī)器模型； 研究機(jī)器能做什么，不能做什么，從

3、而定義劃分可計(jì)算研究機(jī)器能做什么，不能做什么，從而定義劃分可計(jì)算問(wèn)題和不可計(jì)算問(wèn)題。問(wèn)題和不可計(jì)算問(wèn)題。 發(fā)展過(guò)程發(fā)展過(guò)程 1930s，圖靈提出圖靈機(jī)模型；，圖靈提出圖靈機(jī)模型； 19401950s，有限狀態(tài)自動(dòng)機(jī)方面的研究；，有限狀態(tài)自動(dòng)機(jī)方面的研究； 1969年，庫(kù)克分離出了能有效解決的問(wèn)題和難解問(wèn)題。年，庫(kù)克分離出了能有效解決的問(wèn)題和難解問(wèn)題。形式語(yǔ)言與自動(dòng)機(jī)理論的應(yīng)用有限狀態(tài)自動(dòng)機(jī)是描述許多重要硬件和軟件的有用模型。只有有限個(gè)有限狀態(tài)自動(dòng)機(jī)是描述許多重要硬件和軟件的有用模型。只有有限個(gè)狀態(tài)，使得可以用有限的資源來(lái)實(shí)現(xiàn)。狀態(tài)，使得可以用有限的資源來(lái)實(shí)現(xiàn)。 字符串匹配算法字符串匹配算法(K

4、MP) 詞法分析器詞法分析器 設(shè)計(jì)和檢驗(yàn)數(shù)字電路行為的軟件設(shè)計(jì)和檢驗(yàn)數(shù)字電路行為的軟件 其它一些軟件，如通信協(xié)議驗(yàn)證其它一些軟件，如通信協(xié)議驗(yàn)證 與有限自動(dòng)機(jī)有關(guān)的兩種符號(hào)表示與有限自動(dòng)機(jī)有關(guān)的兩種符號(hào)表示 文法：設(shè)計(jì)處理遞歸結(jié)構(gòu)數(shù)據(jù)的軟件的模型文法：設(shè)計(jì)處理遞歸結(jié)構(gòu)數(shù)據(jù)的軟件的模型 正規(guī)表達(dá)式：與自動(dòng)機(jī)描述的字符串模式等價(jià)正規(guī)表達(dá)式：與自動(dòng)機(jī)描述的字符串模式等價(jià) 自動(dòng)機(jī)是研究計(jì)算復(fù)雜性的必要基礎(chǔ)自動(dòng)機(jī)是研究計(jì)算復(fù)雜性的必要基礎(chǔ) 可判定性問(wèn)題：可判定問(wèn)題和不可判定問(wèn)題可判定性問(wèn)題：可判定問(wèn)題和不可判定問(wèn)題 可處理性問(wèn)題：一般問(wèn)題和難解問(wèn)題可處理性問(wèn)題：一般問(wèn)題和難解問(wèn)題計(jì)算機(jī)與人腦觀點(diǎn)一：計(jì)算

5、機(jī)的能力不如人腦的能力觀點(diǎn)一：計(jì)算機(jī)的能力不如人腦的能力 計(jì)算機(jī)無(wú)法解決不可判定問(wèn)題；計(jì)算機(jī)無(wú)法解決不可判定問(wèn)題； 人腦能夠部分解決不可判定問(wèn)題；人腦能夠部分解決不可判定問(wèn)題；例如：判定任意一個(gè)程序是否輸出例如：判定任意一個(gè)程序是否輸出“hello world”。 觀點(diǎn)二：計(jì)算機(jī)的能力與人腦的能力相當(dāng)觀點(diǎn)二：計(jì)算機(jī)的能力與人腦的能力相當(dāng) 人腦由神經(jīng)元細(xì)胞構(gòu)成，每個(gè)神經(jīng)元相當(dāng)于一個(gè)有限狀態(tài)自動(dòng)機(jī)，神人腦由神經(jīng)元細(xì)胞構(gòu)成，每個(gè)神經(jīng)元相當(dāng)于一個(gè)有限狀態(tài)自動(dòng)機(jī)，神經(jīng)經(jīng)元之間的連接是不斷變化的，所以人腦相當(dāng)于一個(gè)極其復(fù)雜的不斷變化的元之間的連接是不斷變化的，所以人腦相當(dāng)于一個(gè)極其復(fù)雜的不斷變化的有限狀態(tài)

6、自動(dòng)機(jī)；有限狀態(tài)自動(dòng)機(jī)； 計(jì)算機(jī)能夠模擬所有圖靈機(jī)，也就能夠模擬所有有限狀態(tài)自動(dòng)機(jī)。計(jì)算機(jī)能夠模擬所有圖靈機(jī)，也就能夠模擬所有有限狀態(tài)自動(dòng)機(jī)。第一章語(yǔ)言 1.1 1.1 語(yǔ)言的定義語(yǔ)言的定義 語(yǔ)言學(xué)家語(yǔ)言學(xué)家chomsky,chomsky,最初從定義語(yǔ)言的角度研究語(yǔ)言最初從定義語(yǔ)言的角度研究語(yǔ)言.1956.1956年年, ,他將他將語(yǔ)言語(yǔ)言L L定義為定義為字母表字母表中的字符組成的一些中的字符組成的一些串的集合串的集合: : 字母表上按一定規(guī)則定義一個(gè)字母表上按一定規(guī)則定義一個(gè)文法文法, ,該文法所能產(chǎn)生的所有的句該文法所能產(chǎn)生的所有的句子組成的集合就是該文法定義的子組成的集合就是該文法定義

7、的語(yǔ)言語(yǔ)言. .*L1.2 基本概念1.語(yǔ)言研究的三個(gè)方面語(yǔ)言研究的三個(gè)方面（1）表示）表示representation：無(wú)窮語(yǔ)言的表示無(wú)窮語(yǔ)言的表示（2）有窮描述）有窮描述finite description：研究的語(yǔ)言要么是有窮的，要么是可：研究的語(yǔ)言要么是有窮的，要么是可數(shù)無(wú)窮的，這里主要研究可數(shù)無(wú)窮語(yǔ)言的有窮描述。數(shù)無(wú)窮的，這里主要研究可數(shù)無(wú)窮語(yǔ)言的有窮描述。（3）結(jié)構(gòu)）結(jié)構(gòu)structure：語(yǔ)言的結(jié)構(gòu)特征語(yǔ)言的結(jié)構(gòu)特征2.字母表字母表alphabet字母表是一個(gè)字母表是一個(gè)非空有窮非空有窮集合，字母表中的元素稱為該字母表中的符號(hào)。集合，字母表中的元素稱為該字母表中的符號(hào)。例：例：

8、0,1等。等。3.字母表的積運(yùn)算字母表的積運(yùn)算 1 1 2ab a 1 1,b 2 2例：例： 1 1 0,1， 2 2a,b,c 1 1 2 =0a,0b,0c,1a,1b,1c4.字母表字母表 的的n次冪次冪 0 為空串為空串 n n-1 的正閉包：的正閉包： 2 3 4 的克林閉包：的克林閉包： 0 0 1 2 3 例：例： 0,1 +0,1,00,01,10,11,000,001， * ,0,1,00,01,10,11,000,001，直觀定義：直觀定義： *x|x是是 中的若干字符連接而成的字符串中的若干字符連接而成的字符串 x|x是是 中至少一個(gè)字符連接而成的字符串中至少一個(gè)字符連

9、接而成的字符串5.句子句子 sentence 是一個(gè)字母表，對(duì)于是一個(gè)字母表，對(duì)于 上的任何元素上的任何元素x，x叫做叫做 上的一個(gè)句子。上的一個(gè)句子。6. 句子的長(zhǎng)度句子的長(zhǎng)度 x ,句子句子x中字符出現(xiàn)的總個(gè)數(shù)中字符出現(xiàn)的總個(gè)數(shù),記為記為|x| ,長(zhǎng)度為零的字符串長(zhǎng)度為零的字符串稱為空句子稱為空句子.用用 表示表示. 7. n語(yǔ)言語(yǔ)言:對(duì)于任意的對(duì)于任意的 ,L稱為字母表稱為字母表上的一個(gè)語(yǔ)言上的一個(gè)語(yǔ)言. .對(duì)于任意對(duì)于任意一個(gè)一個(gè)xL,xL,x叫做叫做L L的一個(gè)句子的一個(gè)句子. .n例例: =0,1上不同的語(yǔ)言上不同的語(yǔ)言:n00,11n0,1n0,1,00,11n001,01,00

10、01,10n00,11*n00,1*1n0,1*1110,1*L1.3語(yǔ)言的有限描述 遞歸定義是解決無(wú)窮語(yǔ)言的有窮描述的最好方法遞歸定義是解決無(wú)窮語(yǔ)言的有窮描述的最好方法. . 遞歸定義的三要素遞歸定義的三要素: : (1) (1) 基本條款基本條款 (2) (2) 歸納條款歸納條款 (3) (3) 最小性條款最小性條款1.3語(yǔ)言的有限描述例例1：a,b上的所有以上的所有以a打頭，長(zhǎng)度為偶數(shù)的句子。打頭，長(zhǎng)度為偶數(shù)的句子。設(shè)設(shè)L是滿足以上條件的語(yǔ)言，是滿足以上條件的語(yǔ)言，L中元素滿足如下條件：中元素滿足如下條件： （1）aa,ab L （2）若）若u L,則則uaa,uab,uba,ubb L

11、 （3）L中的每個(gè)句子是有限使用（中的每個(gè)句子是有限使用（1）（）（2）所得。）所得。例例2：a,b上沒(méi)有兩個(gè)連續(xù)上沒(méi)有兩個(gè)連續(xù)b的所有句子。的所有句子。設(shè)設(shè)L是滿足以上條件的語(yǔ)言，是滿足以上條件的語(yǔ)言，L中元素滿足如下條件：中元素滿足如下條件：（1） ,b L（2）若）若u L,則則ua,uab L（3）L中的每個(gè)句子均是有限次使用（中的每個(gè)句子均是有限次使用（1）（）（2）所得。）所得。1.3語(yǔ)言的有限描述例例3：La,bbba,b L表示所有含有表示所有含有bb的的a,b的字符串。的字符串。例例4：Laa,bb,ab,ba L表示所有長(zhǎng)度為偶數(shù)的字符串。表示所有長(zhǎng)度為偶數(shù)的字符串。1.4

12、正規(guī)語(yǔ)言及其表示（1）定義：定義： 上的正規(guī)語(yǔ)言，滿足下列定義：上的正規(guī)語(yǔ)言，滿足下列定義：（1） 和和為為 上的正規(guī)語(yǔ)言。上的正規(guī)語(yǔ)言。（2）對(duì)于）對(duì)于 a,a為為 上的正規(guī)語(yǔ)言。上的正規(guī)語(yǔ)言。（3）若）若X，Y為為 上的正規(guī)語(yǔ)言，則上的正規(guī)語(yǔ)言，則XY，XY，X也是也是 上的正規(guī)語(yǔ)言。上的正規(guī)語(yǔ)言。（4）所有）所有 上的正規(guī)語(yǔ)言均是有限次使用（上的正規(guī)語(yǔ)言均是有限次使用（1）（）（2）（）（3）而得。）而得。定義：設(shè)定義：設(shè) 為一字母表，為一字母表， 上的正規(guī)式由如下定義：上的正規(guī)式由如下定義：（1） 和和都是都是 上的正規(guī)式。上的正規(guī)式。（2）任何）任何a，a是是 上的正規(guī)式。上的正規(guī)式

13、。（3）u和和v是是是是 上的正規(guī)式，則上的正規(guī)式，則u|v,uv,u為為 上的正規(guī)式。上的正規(guī)式。（4）所有所有 上的正規(guī)式均是有限次使用（上的正規(guī)式均是有限次使用（1）（）（2）（）（3）而得。）而得。正規(guī)語(yǔ)言和正規(guī)式一一對(duì)應(yīng)正規(guī)語(yǔ)言和正規(guī)式一一對(duì)應(yīng)1.4正規(guī)語(yǔ)言及其表示（2）設(shè)設(shè) =a，b， 上的正規(guī)式和相應(yīng)的正規(guī)集有：上的正規(guī)式和相應(yīng)的正規(guī)集有：正規(guī)式正規(guī)式 正規(guī)集正規(guī)集 a a a b a，b ab ab a* ，a，aa，aaa， a*b b，ab，aab，aaab，（a b）* ，a，b，aa，bb，ab，ba，a和和b的任的任 意符號(hào)串意符號(hào)串1.4正規(guī)語(yǔ)言及其表示（3）已知字

14、母表已知字母表a,b，試構(gòu)造其上的正規(guī)式，試構(gòu)造其上的正規(guī)式（1）以）以aa打頭的所有符號(hào)串的集合。打頭的所有符號(hào)串的集合。aa(a|b)*（2）以）以aa結(jié)尾的所有串的集合。結(jié)尾的所有串的集合。 (a|b)* aa（3）每個(gè)）每個(gè)a有一個(gè)也僅有一個(gè)有一個(gè)也僅有一個(gè)b緊跟其后的所有串的集合。緊跟其后的所有串的集合。 b *(ab) *（4）每個(gè)）每個(gè)a有一個(gè)至少有一個(gè)有一個(gè)至少有一個(gè)b緊跟其后的所有串的集合。緊跟其后的所有串的集合。 b *(abb *) *（5）至少包含一個(gè)）至少包含一個(gè)a且且 每個(gè)每個(gè)a都有都有b緊跟其后的所有串的集合。緊跟其后的所有串的集合。 b *ab(b|ab) *1

15、.4 正規(guī)式的性質(zhì)正規(guī)式的性質(zhì) （1）r s=s r （2）r （s t）=（r s） t （3）（）（rs）t=r（st） （4）r（s t）=rs rt （s t）r=sr tr （5） r=r r =r2 文法與語(yǔ)言例例1：已知語(yǔ)言：已知語(yǔ)言L a,b*且且 中中a的個(gè)數(shù)為偶數(shù)的個(gè)數(shù)為偶數(shù)SaA （A中中a的個(gè)數(shù)為奇數(shù)，的個(gè)數(shù)為奇數(shù)，b任意）任意） SbS (S中中a的個(gè)數(shù)為奇數(shù)，的個(gè)數(shù)為奇數(shù)，b任意）任意） A aS bA例例2：已知語(yǔ)言已知語(yǔ)言L a,b*且且 中中a，b的個(gè)數(shù)為相同的個(gè)數(shù)為相同 SaA bB A bS aAA BaS bBB例例3： L（G（S）= | 0,1* 其

16、中其中 中中0的個(gè)數(shù)為偶數(shù)且如果存在的個(gè)數(shù)為偶數(shù)且如果存在1的話必須至少有兩個(gè)連續(xù)的的話必須至少有兩個(gè)連續(xù)的1 S0A（0奇，奇，1符合題意）符合題意） S11B（0偶，偶，1任意）任意） A0S A1C（0奇，奇，1打頭）打頭） B0D（0奇，奇，1任意）任意） B1B （0偶，偶，1任意）任意） C1D （0奇，奇，1任意）任意） D0B （0偶，偶，1任意）任意） D 1D （0奇，奇，1任意）任意） 例例4：L（G（S）= | 0,1* 其中其中 中至少包含一個(gè)中至少包含一個(gè)1且且 每個(gè)每個(gè)1都有都有0緊跟其后緊跟其后 S 1A（A為為0打頭，打頭，1符合題意）符合題意） S 0S A

17、 0B （B為為 0任意，任意，1符合題意）符合題意） B 0B B 1A（ A為為0打頭，打頭，1符合題意）符合題意） 例例5：L a Ra,b，其中，其中 R為為 的逆的逆S a aSa bSb Example 6:Construct a grammar over a,b,c whose language is anb2ncm|n,m0Example 7: Construct a grammar over a,b,c whose language is anbmc2n+m|n,m0 S aScc aBcc B bBb bbExample 8: Construct a grammar ove

18、r a,b,c whose language is anbmci|0n+mi S aSbcc B A A aAc C B bBc C C aC Example 9: Construct a grammar over a,b whose language is anbm|0nm2n S aSb aSbb 右線性文法右線性文法：文法中每條規(guī)則形如：文法中每條規(guī)則形如A a或或A aB，其中，其中a為終為終結(jié)符或結(jié)符或 ，A，B為非終結(jié)符。為非終結(jié)符。左線性文法左線性文法：文法中每條規(guī)則形如：文法中每條規(guī)則形如A a或或A Ba，其中，其中a為終為終結(jié)符，結(jié)符，A，B為非終結(jié)符。為非終結(jié)符。例例 ：

19、給出語(yǔ)言：給出語(yǔ)言Lan bm ck n,m,k=0的左線性和右線性文的左線性和右線性文法。法。左線性文法為：左線性文法為：S Sc B B Bb A A Aa 右線性文法為：右線性文法為： S aS B B bB C C cC 第3章 上下文無(wú)關(guān)語(yǔ)言3.1 上下文無(wú)關(guān)文法一、定義:文法G=(V,T,P,S)稱為上下文無(wú)關(guān)文法,如果P中的每一條規(guī)則具有形式:其中AV,x(VT)*例：文法G=（S，A，B，S，P），產(chǎn)生式這個(gè)文法是上下文無(wú)關(guān)的，它的推導(dǎo)是： S aSa aaSaa aabSbaa aabbaa其定義的語(yǔ)言為其定義的語(yǔ)言為xA |bSbaSaS *,|)(baGLR試證明語(yǔ)言 是

20、上下文無(wú)關(guān)的。證明：當(dāng)nm時(shí)： n0,j0不是正規(guī)語(yǔ)言。不是正規(guī)語(yǔ)言。證明：設(shè)證明：設(shè) ai bj cj |i0,j0是正規(guī)語(yǔ)言。是正規(guī)語(yǔ)言。對(duì)于泵長(zhǎng)度對(duì)于泵長(zhǎng)度N，考慮，考慮z=a bN cN .根據(jù)泵作用引理，根據(jù)泵作用引理，z可分解為如下兩種形式：可分解為如下兩種形式：（1）a v，有，有u v w abi bj bN-i-jcN (其中，其中，i+j0) 考慮考慮uv2w= abibjbjbN-i-jcN =abNbjcN L (2)a v,有有u v w abi bN-icN (其中，其中，i0,j0不是正規(guī)語(yǔ)言。不是正規(guī)語(yǔ)言。例例2：試證明語(yǔ)言：試證明語(yǔ)言L ai bj c2j |

21、i 0,j 0不是正規(guī)語(yǔ)言。不是正規(guī)語(yǔ)言。 6上下文無(wú)關(guān)文法與下推自動(dòng)機(jī) 語(yǔ)言語(yǔ)言ai bi|i0是不能被有窮自動(dòng)機(jī)所接受的。要接受這個(gè)語(yǔ)言，機(jī)是不能被有窮自動(dòng)機(jī)所接受的。要接受這個(gè)語(yǔ)言，機(jī)器需要記錄某一器需要記錄某一a的有限次數(shù)，有限狀態(tài)機(jī)的約束不允許自動(dòng)機(jī)的有限次數(shù)，有限狀態(tài)機(jī)的約束不允許自動(dòng)機(jī)“記住記住”輸輸入入串中串中a的個(gè)數(shù)。因此我們需要定義一個(gè)新型自動(dòng)機(jī)，它由一個(gè)下推棧加上一的個(gè)數(shù)。因此我們需要定義一個(gè)新型自動(dòng)機(jī)，它由一個(gè)下推棧加上一個(gè)有限自動(dòng)機(jī)組成，稱為下推自動(dòng)機(jī)（個(gè)有限自動(dòng)機(jī)組成，稱為下推自動(dòng)機(jī)（PDA）。）。 6.1 下推自動(dòng)機(jī)(1) 定義：下推自動(dòng)機(jī)（定義：下推自動(dòng)機(jī)（pu

22、shdown automation)是一個(gè)七元組是一個(gè)七元組（Q， ， ， ，q0，z,F）,其中其中Q是一有窮狀態(tài)集，是一有窮狀態(tài)集， 為一有窮字母表，為一有窮字母表， 為一有一有窮下推集，為一有一有窮下推集， q0為開始狀態(tài)，為開始狀態(tài)，z為下推字符為下推字符,F Q是終止?fàn)顟B(tài)集，是終止?fàn)顟B(tài)集， 是從是從Q （ ） （ P ）到）到Q （ P ）的轉(zhuǎn)移函數(shù)。）的轉(zhuǎn)移函數(shù)。一個(gè)一個(gè)PDA有兩個(gè)字符集：輸入字符串有兩個(gè)字符集：輸入字符串 它由輸入字符串組成，有一個(gè)棧它由輸入字符串組成，有一個(gè)棧字符集字符集P，它的元素存在棧中。，它的元素存在棧中。A 表示以表示以A為棧頂元素的棧，空棧被表示為棧

23、頂元素的棧，空棧被表示為為 。PDA的計(jì)算開始于狀態(tài)的計(jì)算開始于狀態(tài)q0 ，輸入在輸入帶上且棧為空。，輸入在輸入帶上且棧為空。PDA的當(dāng)前狀態(tài)、輸入符號(hào)和棧頂符號(hào)決定自動(dòng)機(jī)的轉(zhuǎn)換。轉(zhuǎn)換函數(shù)的當(dāng)前狀態(tài)、輸入符號(hào)和棧頂符號(hào)決定自動(dòng)機(jī)的轉(zhuǎn)換。轉(zhuǎn)換函數(shù) 列出所有給定狀態(tài)、符號(hào)和棧頂元素的所有可能的轉(zhuǎn)換。列出所有給定狀態(tài)、符號(hào)和棧頂元素的所有可能的轉(zhuǎn)換。 （ qi，a,A)=qj,B,qk,C表示當(dāng)前狀態(tài)為表示當(dāng)前狀態(tài)為qi，輸入符號(hào)為，輸入符號(hào)為a，棧頂符號(hào)為棧頂符號(hào)為A時(shí)的兩種可能的轉(zhuǎn)換。時(shí)的兩種可能的轉(zhuǎn)換。 6.1 下推自動(dòng)機(jī)(2) qj,B （ qi，a，A) new state current

24、 stack top new stack top current input symbol current state 表示表示 i)狀態(tài)由狀態(tài)由qi換為換為qi ii)處理字符處理字符a,輸入帶向前移動(dòng)輸入帶向前移動(dòng)iii）棧頂）棧頂A退棧退棧iv）B進(jìn)棧。進(jìn)棧。6.1 下推自動(dòng)機(jī)(3) 一個(gè)下推自動(dòng)也可由狀態(tài)轉(zhuǎn)換圖表示，弧上的符號(hào)表示輸入符號(hào)和棧操作。一個(gè)下推自動(dòng)也可由狀態(tài)轉(zhuǎn)換圖表示，弧上的符號(hào)表示輸入符號(hào)和棧操作。轉(zhuǎn)換函轉(zhuǎn)換函qj,B （ qi，a，A) 表示如下：表示如下： a A/Bqi qj 符號(hào)符號(hào)/表示表示B代替代替A 可以出現(xiàn)在輸入字符和棧頂位置，分別三種轉(zhuǎn)換函數(shù)?？梢猿霈F(xiàn)在

25、輸入字符和棧頂位置，分別三種轉(zhuǎn)換函數(shù)。（1） qi, （ qi， ，A) （輸入位置是（輸入位置是 ） A/ A出棧出棧 qi 6.1 下推自動(dòng)機(jī)(4) （2） qi, A （ qi， ， ) （輸入位置是（輸入位置是 ） /A （A壓棧，不改變輸入狀態(tài)）壓棧，不改變輸入狀態(tài)） qi（3） qj, （ qi， a ， ) a / (等價(jià)于有限自動(dòng)機(jī)，轉(zhuǎn)換由狀態(tài)和輸入符號(hào)決定）等價(jià)于有限自動(dòng)機(jī)，轉(zhuǎn)換由狀態(tài)和輸入符號(hào)決定） qi qj一個(gè)一個(gè)PDA可表示為一個(gè)三元組可表示為一個(gè)三元組qi, , ， qi是機(jī)器狀態(tài)，是機(jī)器狀態(tài)， 為未處理為未處理的輸入串的輸入串, 為棧頂。為棧頂。 qi, , qj

26、,v, 表示表示qj,v, 由由qi, , 經(jīng)一步轉(zhuǎn)換而得。經(jīng)一步轉(zhuǎn)換而得。6.1 下推自動(dòng)機(jī)(5) 例例1：構(gòu)造一個(gè)：構(gòu)造一個(gè)PDA接受語(yǔ)言接受語(yǔ)言ai bi |i=0 M: Q=q0, q1 a /A b A/ b A/ =a,b =A F=q0, q1 (q0,a, )=q0,A (q0,b, A)=q1, (q1,b, A)=q1, q0,aabb, q0,abb, A q0,bb, AA q0,b, A q0, , q0 q16.1 下推自動(dòng)機(jī)(6) 定義：設(shè)定義：設(shè)M （Q， ， ， ，q0，F(xiàn)）為一）為一PDA，字符串，字符串 被被PDA接受，如果接受，如果q0, , * * q

27、i, , , qi F（終態(tài)的集合）（終態(tài)的集合）例例2：PDAM接受語(yǔ)言接受語(yǔ)言 c R| a,b*M: Q=q0, q1 =a,b,c =A,B F= q1 (q0,a, )=q0,A b b /B b B/ (q0,b, )=q0, B a /A a A/ (q0,c, )=q1, q0 c / q1 (q1,a, A)=q1, (q1,b, B)=q1, 6.1 下推自動(dòng)機(jī)(7) 例例3：PDAM接受語(yǔ)言接受語(yǔ)言 ai |i=0 ai bi |i=0 a /A b A/ q0 b A/ b A/ q1 / q2 A/ 6.1 下推自動(dòng)機(jī)(8) 例例4:含有相同個(gè)數(shù)的含有相同個(gè)數(shù)的0和和

28、1的所有的的所有的0,1串。串。思想：用棧記錄思想：用棧記錄0 0和和1 1個(gè)數(shù)的差。當(dāng)個(gè)數(shù)的差。當(dāng)1 1比比0 0多時(shí)，棧中全部為多時(shí)，棧中全部為A A，且，且A A的個(gè)數(shù)等的個(gè)數(shù)等于于1 1比比0 0多的個(gè)數(shù)；當(dāng)多的個(gè)數(shù)；當(dāng)0 0比比1 1多時(shí)，棧中全部為多時(shí)，棧中全部為B B，且，且B B的個(gè)數(shù)等于的個(gè)數(shù)等于0 0比比1 1多的多的個(gè)數(shù)。個(gè)數(shù)。 M=(q,p, 0,1, A,B,Z, M=(q,p, 0,1, A,B,Z, , q, Z, p), q, Z, p)，其中，其中 (q,(q, ,Z)=(p, ,Z)=(p, ) ) 接受接受 ，讀完字符串后棧中沒(méi)有，讀完字符串后棧中沒(méi)有A

29、A或或B B，轉(zhuǎn)到終止?fàn)顟B(tài)，轉(zhuǎn)到終止?fàn)顟B(tài) (q,1,Z)=(q, A) (q,1,Z)=(q, A) 在前面在前面0 0和和1 1個(gè)數(shù)相等的時(shí)候又讀到個(gè)數(shù)相等的時(shí)候又讀到1 1，則在棧中壓入，則在棧中壓入1 1個(gè)個(gè)A A (q,0,Z)=(q, B) (q,0,Z)=(q, B) 在前面在前面0 0和和1 1個(gè)數(shù)相等的時(shí)候又讀到個(gè)數(shù)相等的時(shí)候又讀到0 0，則在棧中壓入，則在棧中壓入1 1個(gè)個(gè)B B (q,1,A)=(q, AA) (q,1,A)=(q, AA) 在前面在前面1 1比比0 0個(gè)數(shù)多的時(shí)候又讀到個(gè)數(shù)多的時(shí)候又讀到1 1，則在棧中再壓入，則在棧中再壓入1 1個(gè)個(gè)A A (q,0,A)

30、=(q, (q,0,A)=(q, ) ) 在前面在前面1 1比比0 0個(gè)數(shù)多的時(shí)候又讀到個(gè)數(shù)多的時(shí)候又讀到0 0，則從棧中彈出，則從棧中彈出1 1個(gè)個(gè)A A (q,1,B)=(q, (q,1,B)=(q, ) ) 在前面在前面0 0比比1 1個(gè)數(shù)多的時(shí)候又讀到個(gè)數(shù)多的時(shí)候又讀到1 1，則從棧中彈出，則從棧中彈出1 1個(gè)個(gè)B B (q,0,B)=(q, BB) (q,0,B)=(q, BB) 在前面在前面0 0比比1 1個(gè)數(shù)多的時(shí)候又讀到個(gè)數(shù)多的時(shí)候又讀到0 0，則在棧中壓入，則在棧中壓入1 1個(gè)個(gè)B B根據(jù)文法構(gòu)造根據(jù)文法構(gòu)造 G G：S S1S0S | 0S1S | 1S0S | 0S1S

31、| 構(gòu)造語(yǔ)言的 NPDA30 |nmnbaLmn6.2 下推自動(dòng)機(jī)與上下文無(wú)關(guān)文法一個(gè)上下文無(wú)關(guān)語(yǔ)言都存在一個(gè)NPDA能夠授受它;反之亦然.1.上下文無(wú)關(guān)語(yǔ)言相應(yīng)的下推自動(dòng)機(jī) 對(duì)于每一個(gè)上下文無(wú)關(guān)文法語(yǔ)言都存在一個(gè)NPDA可以接受它.它的基本思想是構(gòu)造一個(gè)NPDA能夠以某種方式對(duì)于該語(yǔ)言中任何符號(hào)串產(chǎn)生一個(gè)最左推導(dǎo).為了對(duì)命題稍做簡(jiǎn)化,我們可以假定上下文無(wú)關(guān)語(yǔ)言是由格里巴克范式生成的.定理:對(duì)于任何的上下文無(wú)關(guān)文法語(yǔ)言L,存在一個(gè)NPDA M使得L=L(M).已知文法SaSbb|a,構(gòu)造NPDA.首先修改文法轉(zhuǎn)換為格里巴克范式: SaSA|a AbB Bb2.下推自動(dòng)機(jī)相應(yīng)的上下文無(wú)關(guān)文法 使

32、用文法模擬PDA的轉(zhuǎn)移,這也就是說(shuō)使句型中的變量部分反映棧的內(nèi)容,而已處理的輸入作為句型的僅含終結(jié)符前綴.為了簡(jiǎn)單,我們將假定問(wèn)題中的NPDA滿足如下條件:(1)它只有一個(gè)終態(tài)qf,且當(dāng)且僅當(dāng)棧空是才進(jìn)入終態(tài).(2)所有轉(zhuǎn)移函數(shù)的形式應(yīng)該是(qi,a,A)=c1,c2,cn,其中C=(qj, )或C=(qj, BC)定理:對(duì)于任何一個(gè)NPDA M,如果L=L(M),則L是上下文無(wú)關(guān)語(yǔ)言.6.36.3 上下文無(wú)關(guān)語(yǔ)言的性質(zhì)上下文無(wú)關(guān)語(yǔ)言的性質(zhì)( (泵引理）泵引理）(1)(1) 定理：定理：(2型語(yǔ)言的泵作用引理型語(yǔ)言的泵作用引理) ) 設(shè)設(shè)L L是上下文無(wú)關(guān)語(yǔ)言，存在常數(shù)是上下文無(wú)關(guān)語(yǔ)言，存在常

33、數(shù)p p，如果，如果LL，且，且p,p,則則可以可以寫為寫為uvwxyuvwxy，其中其中i) vxi) vx，ii)vwxpii)vwxp iii) uvuvi iwxwxi iyLyL (i0i0 ) 線性語(yǔ)言的泵作用引理是說(shuō)，在正規(guī)集合中，每個(gè)足夠長(zhǎng)的字符串都包線性語(yǔ)言的泵作用引理是說(shuō)，在正規(guī)集合中，每個(gè)足夠長(zhǎng)的字符串都包含一個(gè)短的字串，隨便將這個(gè)子串在原處重復(fù)插入多少次，所得的新字串含一個(gè)短的字串，隨便將這個(gè)子串在原處重復(fù)插入多少次，所得的新字串還是在原正規(guī)集中。還是在原正規(guī)集中。 2 2型語(yǔ)言的泵引理是說(shuō)，有兩個(gè)靠得很近的子串，它們可以重復(fù)任意型語(yǔ)言的泵引理是說(shuō)，有兩個(gè)靠得很近的子串

34、，它們可以重復(fù)任意多次（但二者重復(fù)的次數(shù)相同），所得的新串依然屬于該多次（但二者重復(fù)的次數(shù)相同），所得的新串依然屬于該2 2型語(yǔ)言。型語(yǔ)言。 6.36.3上下文無(wú)關(guān)語(yǔ)言的性質(zhì)上下文無(wú)關(guān)語(yǔ)言的性質(zhì)( (泵引理）泵引理）(2)(2) 證明證明 L L an bn cn | n n1 1 不是不是2 2型語(yǔ)言型語(yǔ)言. .證：假設(shè)證：假設(shè)L L是是2 2型語(yǔ)言。型語(yǔ)言。 取常數(shù)取常數(shù)p p， ap bp cp, ,3p3pp p 將將寫成寫成uvwxyuvwxy 其中其中vx1 vx1 且且 vwxvwxp p 考慮考慮vwxvwx在在中所處的位置：中所處的位置： 如果如果v v含有含有a a，x x

35、含有含有c c， apbpcp 則有則有vwxvwx最小為最小為a a bp c c p+2 pp+2 p 不滿足泵作用引理的條件。不滿足泵作用引理的條件。 如果如果v,xv,x都含有都含有a a，（，（b b或或c c） ap bp cp 可寫成可寫成a ai ap-2-i-j a aj j bp cp v w x v w x 將將v v、x x重復(fù)重復(fù)2 2次，將有次，將有 = = a2iap-2-i-j a2j bp cp L(a L(a的個(gè)數(shù)大于的個(gè)數(shù)大于b b和和c c的個(gè)數(shù)的個(gè)數(shù)) ) 與與2 2型語(yǔ)言的假設(shè)矛盾型語(yǔ)言的假設(shè)矛盾6.36.3上下文無(wú)關(guān)語(yǔ)言的性質(zhì)上下文無(wú)關(guān)語(yǔ)言的性質(zhì)(

36、 (泵引理）泵引理）(3)(3) 若若v v、x x分別包含分別包含a a和和b b（b b和和c c） 當(dāng)取當(dāng)取w w = = a a a a ap-2b b bp-1 cp 時(shí)時(shí) u v w x yu v w x y 將將v v、x x重復(fù)重復(fù)2 2次，次， 將有將有 = a = a a a2 2 ap-2b b2 2 bp-1 cp L L v w x v w x （其中其中a a、b b個(gè)數(shù)將大于個(gè)數(shù)將大于c c的個(gè)數(shù)）的個(gè)數(shù)） 與與2 2型語(yǔ)言假設(shè)矛盾。型語(yǔ)言假設(shè)矛盾。 綜上，綜上，L L不是不是2 2型語(yǔ)言。型語(yǔ)言。 6.36.3上下文無(wú)關(guān)語(yǔ)言的性質(zhì)上下文無(wú)關(guān)語(yǔ)言的性質(zhì)( (泵引理

37、）泵引理）(4)(4) 證明：證明：La*| 的長(zhǎng)度為質(zhì)數(shù)不是上下文無(wú)關(guān)文法。的長(zhǎng)度為質(zhì)數(shù)不是上下文無(wú)關(guān)文法。證明：設(shè)證明：設(shè)L是上下文無(wú)關(guān)文法，是上下文無(wú)關(guān)文法，n是一個(gè)大于泵作用引理中是一個(gè)大于泵作用引理中p的素?cái)?shù)的素?cái)?shù). 由泵作用引理知：由泵作用引理知： an必須分解為必須分解為uvwxy滿足泵引理的條件令滿足泵引理的條件令mu|+|w|+|y|,任意串任意串uvuvi iwxwxi iy y的長(zhǎng)度是的長(zhǎng)度是m+i(n-m).m+i(n-m). |uv |uvn+1n+1|+|wx|+|wxn+1n+1|+|y|=m+(n+1)(n-m)=n(n-m+1)|+|y|=m+(n+1)(n-

38、m)=n(n-m+1) 故故uvuvi iwxwxi iy y的長(zhǎng)度不是質(zhì)數(shù)，所以的長(zhǎng)度不是質(zhì)數(shù)，所以L L不是上下文無(wú)關(guān)文法。不是上下文無(wú)關(guān)文法。 證明語(yǔ)言證明語(yǔ)言an bjanbj |i,j=0不是上下文無(wú)關(guān)語(yǔ)言。不是上下文無(wú)關(guān)語(yǔ)言。6.36.3上下文無(wú)關(guān)語(yǔ)言的性質(zhì)上下文無(wú)關(guān)語(yǔ)言的性質(zhì)( (封閉性）封閉性） （1 1）設(shè)有）設(shè)有2型語(yǔ)言型語(yǔ)言L1、L2，則則L1L2，L1L2，L1* 為為2型語(yǔ)言。型語(yǔ)言。（2 2）2 2型語(yǔ)言對(duì)交不封閉型語(yǔ)言對(duì)交不封閉 反證：取反例反證：取反例 L1L1aan n b bn nc cmm m,nm,n1 21 2型型 L2L2 a am m b bn n

39、c cn nm,nm,n1 21 2型型 L1L1L2L2aan n b bn nc cn n n n1 1 不是不是2 2型型 （3 3）2 2型語(yǔ)言對(duì)補(bǔ)運(yùn)算不封閉型語(yǔ)言對(duì)補(bǔ)運(yùn)算不封閉L1L1L2= L1L2= L1L2L2若對(duì)補(bǔ)封閉，則對(duì)交封閉。若對(duì)補(bǔ)封閉，則對(duì)交封閉。已知對(duì)交不封閉，已知對(duì)交不封閉，對(duì)補(bǔ)不封閉對(duì)補(bǔ)不封閉 第七章 圖靈機(jī)標(biāo)準(zhǔn)圖靈機(jī) 圖靈機(jī)可以看成一個(gè)一維單元組,其中每一個(gè)單元可以包含一個(gè)符號(hào).該單元組可以在兩端無(wú)限擴(kuò)展,因此它能夠存儲(chǔ)無(wú)窮信息.這些信息可以以任意順序讀取和修改,我們稱這樣的存儲(chǔ)機(jī)制為帶(tape),因?yàn)樗c實(shí)際計(jì)算機(jī)的磁帶十分類似.圖靈機(jī)的定義圖靈機(jī)是一種自

40、動(dòng)機(jī)，它采用帶作為臨時(shí)存儲(chǔ)，帶可以劃分為若干單元，其中每一個(gè)單元包含一個(gè)符號(hào)。與帶關(guān)聯(lián)的是讀寫頭(read-write head)，它能夠在帶上左右移動(dòng)，并且每次能夠讀寫一個(gè)符號(hào)。下圖圖靈機(jī)的直觀描述。圖靈機(jī)的直觀描述控制部件讀寫頭帶圖靈機(jī)的形式定義 圖靈機(jī)M由 M=（Q,q0,F)定義，其中： Q是內(nèi)部狀態(tài)的集合； 是輸入字母表 是符號(hào)的有窮集合，稱之為帶字母表（tape alphabet) 是轉(zhuǎn)換函數(shù) 是一個(gè)特殊符號(hào)，稱之為空白符（blank) q0Q是初態(tài)，F(xiàn) Q為終態(tài)的集合。 在圖靈機(jī)的定義中我們假定-，也就是說(shuō)輸入字母表是帶字母表的子集。轉(zhuǎn)換函數(shù)定義如下： ：QQ L，R 它給出了圖

41、靈機(jī)操作的規(guī)則。 的參數(shù)是控制部件的當(dāng)前狀態(tài)以及即將讀入的帶符號(hào)，它的返回結(jié)果是一個(gè)新的控制部件狀態(tài)、一個(gè)替換舊帶符號(hào)的新符號(hào)以及一個(gè)遷移符號(hào)L和R（讀頭的移動(dòng)方向：向左或向右）abc內(nèi)部狀態(tài)q0遷移前的情形dbc內(nèi)部狀態(tài)q1遷移后的情形下圖顯示了轉(zhuǎn)換函數(shù)（q0,a)=(q1,d,R)執(zhí)行前后的情形： 通常，自動(dòng)機(jī)以一個(gè)給定的初態(tài)和帶上的一些信息開始。然后在轉(zhuǎn)移函數(shù)的控制下完成一系列的動(dòng)作。在這一過(guò)程中，帶上任何一個(gè)單元的內(nèi)容可能會(huì)被檢查與修改，最后通過(guò)將圖靈機(jī)置于停機(jī)狀態(tài)（halt state) 使整個(gè)過(guò)程結(jié)束。當(dāng)圖靈機(jī)到達(dá)一個(gè)中沒(méi)有定義的格局時(shí)，將會(huì)停機(jī)。 一個(gè)圖靈機(jī)及初始格局遷移片斷例：

42、Q=q0,q1 =a,b =a,b, F=q1 (q0,a)=q0,b,R (q0,b)=q0,b,R (q0, )=q1,La aq0b aq0b bq0b bq1從一種格局到加一種格局的遷移可采用表示，如(q0,b)=q0,b,R表示為：bq0b bbq0,因此上式的遷移過(guò)程為： q0aa bq0a bbq0 bq1b 也記為：q0aa * bq1b標(biāo)準(zhǔn)圖靈機(jī)的特征1.圖靈機(jī)的帶在左右方向上都沒(méi)有限制，允許任意數(shù)目的左遷移和右遷移。2.由于對(duì)每一個(gè)格局，最多只定義一種遷移，因而它是確定型的。3.沒(méi)有特定的輸入文件。假定在初始時(shí)刻，帶上存在特定的內(nèi)容，其中部份內(nèi)容可以作為圖靈機(jī)的輸入。同樣沒(méi)

43、有特定的輸出設(shè)備。當(dāng)圖靈機(jī)停機(jī)時(shí)，帶的部份或者全部?jī)?nèi)容可以作為輸出。遷移的形式定義設(shè)圖靈機(jī)M=（Q,q0,F)，則任意串a(chǎn)1ak-1q1akak+1an,其中ai且q1Q ,是M的一個(gè)瞬時(shí)描述。遷移 a1ak-1q1akak+1an a1ak-1bq2ak+1an 是可能的當(dāng)且僅當(dāng)： (q1,ak)=(q2,b,R)遷移 a1ak-1q1akak+1an a1q2ak-1bak+1an 是可能的當(dāng)且僅當(dāng)： (q1,ak)=(q2,b,L)針對(duì)某一初始格局x1qix2,如果x1qix2 *y1qjay2由于對(duì)于任意qj與a， (qj,a)沒(méi)有意義，則M停機(jī)。我們把導(dǎo)致停機(jī)狀態(tài)的格局序列稱為計(jì)算（

44、computation) 作為語(yǔ)言接受器的圖靈機(jī)定義：設(shè) M=（Q,q0,F)是一個(gè)圖靈機(jī)，則被M接受的語(yǔ)言為： L(M)=w+:q0w*x1qfx2 對(duì)于某個(gè)qfF,x1,x2* 例1：基于=0，1，設(shè)計(jì)一個(gè)圖靈機(jī)，它能夠接受正則表達(dá)式00*表達(dá)的語(yǔ)言。 Q=q0,q1 F=q1 轉(zhuǎn)換函數(shù)為： (q0,0)=(q0,0,R) (q0, )=(q1,R)例：對(duì)=a,b，設(shè)計(jì)一個(gè)圖靈機(jī)，它能夠接受L=anbn|n1直觀上，我們可以用下面方式來(lái)解決這一問(wèn)題。從最左邊的a開始，對(duì)其進(jìn)行核對(duì)并以某一符號(hào)比如x替換它。然后我們讓讀頭繼續(xù)右移直到碰到最左邊的b，對(duì)它同樣進(jìn)行核對(duì)并經(jīng)某一符號(hào)比如y替換它。在

45、這之一后，我們又左移到最左邊的a上，用x替換它，然后移至最左邊的b，用y替換它，依此繼續(xù)。通過(guò)這種來(lái)回移動(dòng)，對(duì)每個(gè)a，我們用b去和它匹配，如果最后沒(méi)有a和b了，則認(rèn)為該符號(hào)串一定在語(yǔ)言L中。 Q=q0,q1,q2,q3,q4 F=q4 =a,b =a,b,x,y, (q0,a)=(q1,x,R) (q1,a)=(q1,a,R) (q1,y)=(q1,y,R) (q1,b)=(q2,y,L) (q2,y)=(q2,y,L) (q2,a)=(q2,a,L) (q2,x)=(q0,x,R) (q0,y)=(q3,y,R) (q3,y)=(q3,y,R) (q3,)=(q4,R)作為轉(zhuǎn)換器的圖靈機(jī) 圖

46、靈機(jī)并不僅僅在語(yǔ)言接受上有用,它同樣為我們提供了通用計(jì)算機(jī)的一個(gè)簡(jiǎn)單的抽象模型.由于計(jì)算機(jī)的基本目標(biāo)在于將輸入轉(zhuǎn)換為輸出,它就象一個(gè)轉(zhuǎn)換器的工作一樣. 一個(gè)計(jì)算的輸入就是初始時(shí)刻帶上的空白符號(hào),而計(jì)算完成時(shí),帶上所有的符號(hào)就是輸出.這樣我們可以將一個(gè)圖靈機(jī)轉(zhuǎn)換器看成函數(shù)f的實(shí)現(xiàn).f定義如下:如果對(duì)某一個(gè)終態(tài)qf,e,有 w=f(w) 即:q0w*mqfw定義:對(duì)定義域?yàn)镈的函數(shù)f,如果存在一個(gè)圖靈機(jī)M= (Q,q0,F)使得對(duì)所有的wD,都有q0w*Mqff(w), qfF 成立,則稱該函數(shù)是圖靈可計(jì)算的(Turing-computable)或可計(jì)算的(computable)例:設(shè)計(jì)一個(gè)圖靈機(jī)

47、用于拷貝由1構(gòu)成的符號(hào)串.更確切的說(shuō),也就是構(gòu)造一機(jī)器能夠執(zhí)行計(jì)算: q0w*qfww 其中w1+直觀描述: 1.用x替換每一個(gè)1 2.找到最右邊的x,用1替換它 3.移至當(dāng)前帶上非空區(qū)域的最右端,并創(chuàng)建1 4.重復(fù)2和3直到再也沒(méi)有x為止.其圖靈機(jī)為: (q0,1)=(q0,x,R) (q0, )=(q1, ,L) (q1,x)=(q2,1,R) (q2,1)=(q2,1,R) (q2, )=(q1,1,L) (q1,1)=(q1,1,L) (q1, )=(q3, ,R)其中q3為唯一的終態(tài). q011x q01x xq0 x q0 xx1 q2 為如下基于a,b的語(yǔ)言構(gòu)造圖靈機(jī):nL=L(

48、aba*b)(b) L=a,b*| |是偶數(shù) （q0,a)= (q0,b)=(q1,R) （q0,)= (q2,R) （q1,a)= (q1,b)=(q0,R)其中F=q2.第八章 圖靈機(jī)的其它模型1.帶不動(dòng)選擇圖靈機(jī) 在標(biāo)準(zhǔn)圖靈機(jī)定義中,讀寫頭要么向左移動(dòng)要么向右移動(dòng),而有時(shí)為了方便,我們引入第三種選擇,即在讀寫頭重寫帶上單元后位置保持不動(dòng),于是人們可以修改標(biāo)準(zhǔn)圖靈機(jī)得到新的帶不動(dòng)選擇的圖靈機(jī)(Turing machine with stay-option)的定義,辦法是將標(biāo)準(zhǔn)圖靈機(jī)定義中的替換為: :QQ L,R,S S表示讀寫頭位置保持不動(dòng).這一改動(dòng)并沒(méi)有增強(qiáng)標(biāo)準(zhǔn)圖靈機(jī)的能力.定理:帶不

49、動(dòng)選擇的圖靈機(jī)類與標(biāo)準(zhǔn)圖靈機(jī)類等價(jià).證明:因?yàn)閹Р粍?dòng)選擇圖靈機(jī)顯然是標(biāo)準(zhǔn)圖靈機(jī)的擴(kuò)展,于是任何標(biāo)準(zhǔn)圖靈機(jī)無(wú)疑可以被帶不動(dòng)選擇圖靈機(jī)模擬. 為了證明逆命題,我們令M=（Q,q0,F)為一帶不動(dòng)選擇圖靈機(jī).用一個(gè)標(biāo)準(zhǔn)圖靈機(jī)M=（Q,q0,F)模擬它.對(duì)于M的每一步,模擬機(jī)M做如下工作:如果M的讀寫頭向左移動(dòng)或向右移動(dòng),則M的讀寫頭也相應(yīng)地向左或向右移動(dòng);如果M執(zhí)行了動(dòng)作S,則M執(zhí)行兩步動(dòng)作:讀寫頭首先重寫單元格并向右移動(dòng),然后對(duì)新移動(dòng)到的單元格不做任何修改并向左移動(dòng).這一模擬機(jī)可以愛(ài)過(guò)定義由M構(gòu)造如下:對(duì)于每一步轉(zhuǎn)移 （qi,a)=(qj,b,L or R)我們把解釋為: （qi,a)=(qj,

50、b, L or R)對(duì)于讀寫頭不動(dòng)的轉(zhuǎn)移 （qi,a)=(qj,b,S)我們把讀寫頭解釋為相應(yīng)的兩步轉(zhuǎn)移: （qi,a)=(qjs, b, R) （qjs,c)=(qj, c, L) 其中c很顯然,對(duì)M的每一個(gè)計(jì)算,都有對(duì)應(yīng)的M的一個(gè)計(jì)算,因此M可以模擬M. 模擬是證明自動(dòng)機(jī)等價(jià)的一種標(biāo)準(zhǔn)技術(shù). 在介紹其他模型之前,我們對(duì)標(biāo)準(zhǔn)圖靈機(jī)做一點(diǎn)修改,每個(gè)帶符號(hào)可以是一些符號(hào)的組合體,而不僅僅是單個(gè)符號(hào).在下圖中每個(gè)帶符號(hào)都是三個(gè)較簡(jiǎn)單的字母構(gòu)成的三元組.帶上的每個(gè)單元?jiǎng)澐譃槿齻€(gè)部分,每部分稱為道(track),每個(gè)道包含三元組的一個(gè)成員.基于這一直觀認(rèn)識(shí),這樣的圖靈機(jī)有時(shí)稱為多道圖靈機(jī)(Turing

51、 machine with multiple tracks).但這一觀點(diǎn)并沒(méi)有擴(kuò)展標(biāo)準(zhǔn)圖靈機(jī)的定義,因?yàn)槲覀兯龅闹皇菍⒏臑橐粋€(gè)新的字母表,其中每個(gè)符號(hào)包含幾個(gè)部分.a第一道b第二道c第三道2.單向無(wú)窮帶圖靈機(jī) 單向無(wú)窮帶圖靈機(jī)器(Turing machine with semi-infinite tape) 可以直觀地理解為帶只有左邊界.這一模型與標(biāo)準(zhǔn)模型同樣等價(jià)的,區(qū)別在于當(dāng)讀寫頭位于帶的左邊界時(shí)不能向左移動(dòng). 不難看出,這一限制并沒(méi)有影響村準(zhǔn)圖靈機(jī)的能力. 為了用單向無(wú)窮帶圖靈機(jī)M1模擬標(biāo)準(zhǔn)圖靈機(jī)M,我們采用下圖所示的帶: 模擬帶M1有一條雙帶道,在上道中保存位于M帶上某一點(diǎn)右側(cè)單元的

52、內(nèi)容,如可以選擇計(jì)算開始時(shí)讀頭的位置作為參考點(diǎn).在下道中,我們以逆序保存位于M帶上參考點(diǎn)左側(cè)的內(nèi)容.我們可以可以對(duì)M1編程.使得當(dāng)M的讀寫頭位于參考點(diǎn)右側(cè)時(shí), M1使用上道信息; 當(dāng)M的讀寫頭位于參考點(diǎn)左側(cè)時(shí), M1使用下道信息;M的讀寫頭是否位于參考點(diǎn)右側(cè)可以通過(guò)M1的狀態(tài)分為兩部分以輔助進(jìn)行判斷,比如設(shè)兩類狀態(tài)分別為QU和QL:當(dāng)M1處于上道時(shí)使用前者,否則使用后者.左邊界處的上下道中均包含特殊的結(jié)束符#,以便于兩個(gè)道間的切換. 第一道模擬標(biāo)準(zhǔn)帶的右部第二道模擬標(biāo)準(zhǔn)帶的左部如:被模擬的圖靈機(jī)M和模擬機(jī)M1分別位于下圖所示的格局,并且將要模擬的遷移由（qi,a)=(qj,c,L)生成.模擬機(jī)M1先通過(guò)轉(zhuǎn)移1（q1i,a)=(q1j,(c,b),L)來(lái)進(jìn)行遷移,其中q1i QU,所以此處只考慮上道信息.此時(shí)模擬機(jī)在狀態(tài)q1j QU.因?yàn)閝1i QU,所以此處只考慮上道信息,此時(shí)模擬機(jī)在狀態(tài)q1i QU,看到了符號(hào)(#,#),接下來(lái)作轉(zhuǎn)移: 1（q1j,(#,#)=(p1j,(#,#),R),其中p1j QLabc參考點(diǎn)q1iqi # a # b# a# c# c# b# b# bq1iq1jp1j3.離線圖靈機(jī) 如果我們?cè)谀Ｐ椭屑尤胼斎胛募?我