形式語言與自動機

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

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

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

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

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

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

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

8、0,1等。等。3.字母表的積運算字母表的積運算 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是是 中至少一個字符連接而成的字符串中至少一個字符連

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

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

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

12、正規(guī)語言及其表示（1）定義：定義： 上的正規(guī)語言，滿足下列定義：上的正規(guī)語言，滿足下列定義：（1） 和和為為 上的正規(guī)語言。上的正規(guī)語言。（2）對于）對于 a,a為為 上的正規(guī)語言。上的正規(guī)語言。（3）若）若X，Y為為 上的正規(guī)語言，則上的正規(guī)語言，則XY，XY，X也是也是 上的正規(guī)語言。上的正規(guī)語言。（4）所有）所有 上的正規(guī)語言均是有限次使用（上的正規(guī)語言均是有限次使用（1）（）（2）（）（3）而得。）而得。定義：設定義：設 為一字母表，為一字母表， 上的正規(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ī)語言和正規(guī)式一一對應正規(guī)語言和正規(guī)式一一對應1.4正規(guī)語言及其表示（2）設設 =a，b， 上的正規(guī)式和相應的正規(guī)集有：上的正規(guī)式和相應的正規(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的任的任 意符號串意符號串1.4正規(guī)語言及其表示（3）已知字

14、母表已知字母表a,b，試構造其上的正規(guī)式，試構造其上的正規(guī)式（1）以）以aa打頭的所有符號串的集合。打頭的所有符號串的集合。aa(a|b)*（2）以）以aa結尾的所有串的集合。結尾的所有串的集合。 (a|b)* aa（3）每個）每個a有一個也僅有一個有一個也僅有一個b緊跟其后的所有串的集合。緊跟其后的所有串的集合。 b *(ab) *（4）每個）每個a有一個至少有一個有一個至少有一個b緊跟其后的所有串的集合。緊跟其后的所有串的集合。 b *(abb *) *（5）至少包含一個）至少包含一個a且且 每個每個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 文法與語言例例1：已知語言：已知語言L a,b*且且 中中a的個數(shù)為偶數(shù)的個數(shù)為偶數(shù)SaA （A中中a的個數(shù)為奇數(shù)，的個數(shù)為奇數(shù)，b任意）任意） SbS (S中中a的個數(shù)為奇數(shù)，的個數(shù)為奇數(shù)，b任意）任意） A aS bA例例2：已知語言已知語言L a,b*且且 中中a，b的個數(shù)為相同的個數(shù)為相同 SaA bB A bS aAA BaS bBB例例3： L（G（S）= | 0,1* 其

16、中其中 中中0的個數(shù)為偶數(shù)且如果存在的個數(shù)為偶數(shù)且如果存在1的話必須至少有兩個連續(xù)的的話必須至少有兩個連續(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* 其中其中 中至少包含一個中至少包含一個1且且 每個每個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為終為終結符或結符或 ，A，B為非終結符。為非終結符。左線性文法左線性文法：文法中每條規(guī)則形如：文法中每條規(guī)則形如A a或或A Ba，其中，其中a為終為終結符，結符，A，B為非終結符。為非終結符。例例 ：

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

20、上下文無關的。證明：當nm時： n0,j0不是正規(guī)語言。不是正規(guī)語言。證明：設證明：設 ai bj cj |i0,j0是正規(guī)語言。是正規(guī)語言。對于泵長度對于泵長度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ī)語言。不是正規(guī)語言。例例2：試證明語言：試證明語言L ai bj c2j |

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

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

23、頂元素的棧，空棧被表示為為 。PDA的計算開始于狀態(tài)的計算開始于狀態(tài)q0 ，輸入在輸入帶上且棧為空。，輸入在輸入帶上且棧為空。PDA的當前狀態(tài)、輸入符號和棧頂符號決定自動機的轉(zhuǎn)換。轉(zhuǎn)換函數(shù)的當前狀態(tài)、輸入符號和棧頂符號決定自動機的轉(zhuǎn)換。轉(zhuǎn)換函數(shù) 列出所有給定狀態(tài)、符號和棧頂元素的所有可能的轉(zhuǎn)換。列出所有給定狀態(tài)、符號和棧頂元素的所有可能的轉(zhuǎn)換。 （ qi，a,A)=qj,B,qk,C表示當前狀態(tài)為表示當前狀態(tài)為qi，輸入符號為，輸入符號為a，棧頂符號為棧頂符號為A時的兩種可能的轉(zhuǎn)換。時的兩種可能的轉(zhuǎn)換。 6.1 下推自動機(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,輸入帶向前移動輸入帶向前移動iii）棧頂）棧頂A退棧退棧iv）B進棧。進棧。6.1 下推自動機(3) 一個下推自動也可由狀態(tài)轉(zhuǎn)換圖表示，弧上的符號表示輸入符號和棧操作。一個下推自動也可由狀態(tài)轉(zhuǎn)換圖表示，弧上的符號表示輸入符號和棧操作。轉(zhuǎn)換函轉(zhuǎn)換函qj,B （ qi，a，A) 表示如下：表示如下： a A/Bqi qj 符號符號/表示表示B代替代替A 可以出現(xiàn)在輸入字符和棧頂位置，分別三種轉(zhuǎn)換函數(shù)。可以出現(xiàn)在

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

26、,v, 表示表示qj,v, 由由qi, , 經(jīng)一步轉(zhuǎn)換而得。經(jīng)一步轉(zhuǎn)換而得。6.1 下推自動機(5) 例例1：構造一個：構造一個PDA接受語言接受語言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 下推自動機(6) 定義：設定義：設M （Q， ， ， ，q0，F(xiàn)）為一）為一PDA，字符串，字符串 被被PDA接受，如果接受，如果q0, , * * q

27、i, , , qi F（終態(tài)的集合）（終態(tài)的集合）例例2：PDAM接受語言接受語言 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 下推自動機(7) 例例3：PDAM接受語言接受語言 ai |i=0 ai bi |i=0 a /A b A/ q0 b A/ b A/ q1 / q2 A/ 6.1 下推自動機(8) 例例4:含有相同個數(shù)的含有相同個數(shù)的0和和

28、1的所有的的所有的0,1串。串。思想：用棧記錄思想：用棧記錄0 0和和1 1個數(shù)的差。當個數(shù)的差。當1 1比比0 0多時，棧中全部為多時，棧中全部為A A，且，且A A的個數(shù)等的個數(shù)等于于1 1比比0 0多的個數(shù)；當多的個數(shù)；當0 0比比1 1多時，棧中全部為多時，棧中全部為B B，且，且B B的個數(shù)等于的個數(shù)等于0 0比比1 1多的多的個數(shù)。個數(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, ) ) 接受接受 ，讀完字符串后棧中沒有，讀完字符串后棧中沒有A

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

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

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

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

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

34、，它們可以重復任意多次（但二者重復的次數(shù)相同），所得的新串依然屬于該多次（但二者重復的次數(shù)相同），所得的新串依然屬于該2 2型語言。型語言。 6.36.3上下文無關語言的性質(zhì)上下文無關語言的性質(zhì)( (泵引理）泵引理）(2)(2) 證明證明 L L an bn cn | n n1 1 不是不是2 2型語言型語言. .證：假設證：假設L L是是2 2型語言。型語言。 取常數(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重復重復2 2次，將有次，將有 = = a2iap-2-i-j a2j bp cp L(a L(a的個數(shù)大于的個數(shù)大于b b和和c c的個數(shù)的個數(shù)) ) 與與2 2型語言的假設矛盾型語言的假設矛盾6.36.3上下文無關語言的性質(zhì)上下文無關語言的性質(zhì)(

36、 (泵引理）泵引理）(3)(3) 若若v v、x x分別包含分別包含a a和和b b（b b和和c c） 當取當取w w = = a a a a ap-2b b bp-1 cp 時時 u v w x yu v w x y 將將v v、x x重復重復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個數(shù)將大于個數(shù)將大于c c的個數(shù)）的個數(shù)） 與與2 2型語言假設矛盾。型語言假設矛盾。 綜上，綜上，L L不是不是2 2型語言。型語言。 6.36.3上下文無關語言的性質(zhì)上下文無關語言的性質(zhì)( (泵引理

37、）泵引理）(4)(4) 證明：證明：La*| 的長度為質(zhì)數(shù)不是上下文無關文法。的長度為質(zhì)數(shù)不是上下文無關文法。證明：設證明：設L是上下文無關文法，是上下文無關文法，n是一個大于泵作用引理中是一個大于泵作用引理中p的素數(shù)的素數(shù). 由泵作用引理知：由泵作用引理知： an必須分解為必須分解為uvwxy滿足泵引理的條件令滿足泵引理的條件令mu|+|w|+|y|,任意串任意串uvuvi iwxwxi iy y的長度是的長度是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ì)數(shù)，所以的長度不是質(zhì)數(shù)，所以L L不是上下文無關文法。不是上下文無關文法。 證明語言證明語言an bjanbj |i,j=0不是上下文無關語言。不是上下文無關語言。6.36.3上下文無關語言的性質(zhì)上下文無關語言的性質(zhì)( (封閉性）封閉性） （1 1）設有）設有2型語言型語言L1、L2，則則L1L2，L1L2，L1* 為為2型語言。型語言。（2 2）2 2型語言對交不封閉型語言對交不封閉 反證：取反例反證：取反例 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型語言對補運算不封閉型語言對補運算不封閉L1L1L2= L1L2= L1L2L2若對補封閉，則對交封閉。若對補封閉，則對交封閉。已知對交不封閉，已知對交不封閉，對補不封閉對補不封閉 第七章 圖靈機標準圖靈機 圖靈機可以看成一個一維單元組,其中每一個單元可以包含一個符號.該單元組可以在兩端無限擴展,因此它能夠存儲無窮信息.這些信息可以以任意順序讀取和修改,我們稱這樣的存儲機制為帶(tape),因為它與實際計算機的磁帶十分類似.圖靈機的定義圖靈機是一種自

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

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

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,因此上式的遷移過程為： q0aa bq0a bbq0 bq1b 也記為：q0aa * bq1b標準圖靈機的特征1.圖靈機的帶在左右方向上都沒有限制，允許任意數(shù)目的左遷移和右遷移。2.由于對每一個格局，最多只定義一種遷移，因而它是確定型的。3.沒有特定的輸入文件。假定在初始時刻，帶上存在特定的內(nèi)容，其中部份內(nèi)容可以作為圖靈機的輸入。同樣沒

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

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

45、這之一后，我們又左移到最左邊的a上，用x替換它，然后移至最左邊的b，用y替換它，依此繼續(xù)。通過這種來回移動，對每個a，我們用b去和它匹配，如果最后沒有a和b了，則認為該符號串一定在語言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)換器的圖靈機 圖

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

47、用于拷貝由1構成的符號串.更確切的說,也就是構造一機器能夠執(zhí)行計算: q0w*qfww 其中w1+直觀描述: 1.用x替換每一個1 2.找到最右邊的x,用1替換它 3.移至當前帶上非空區(qū)域的最右端,并創(chuàng)建1 4.重復2和3直到再也沒有x為止.其圖靈機為: (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的語言構造圖靈機: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.第八章 圖靈機的其它模型1.帶不動選擇圖靈機 在標準圖靈機定義中,讀寫頭要么向左移動要么向右移動,而有時為了方便,我們引入第三種選擇,即在讀寫頭重寫帶上單元后位置保持不動,于是人們可以修改標準圖靈機得到新的帶不動選擇的圖靈機(Turing machine with stay-option)的定義,辦法是將標準圖靈機定義中的替換為: :QQ L,R,S S表示讀寫頭位置保持不動.這一改動并沒有增強標準圖靈機的能力.定理:帶不

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

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

51、 machine with multiple tracks).但這一觀點并沒有擴展標準圖靈機的定義,因為我們所要做的只是將改為一個新的字母表,其中每個符號包含幾個部分.a第一道b第二道c第三道2.單向無窮帶圖靈機 單向無窮帶圖靈機器(Turing machine with semi-infinite tape) 可以直觀地理解為帶只有左邊界.這一模型與標準模型同樣等價的,區(qū)別在于當讀寫頭位于帶的左邊界時不能向左移動. 不難看出,這一限制并沒有影響村準圖靈機的能力. 為了用單向無窮帶圖靈機M1模擬標準圖靈機M,我們采用下圖所示的帶: 模擬帶M1有一條雙帶道,在上道中保存位于M帶上某一點右側單元的

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