計(jì)算理論課件第一章.ppt

計(jì)算理論基礎(chǔ),信息科學(xué)與工程學(xué)院 計(jì)算機(jī)軟件與理論研究所,許桂清 楊瑩,序 言,一. 本課的性質(zhì)以及研究的內(nèi)容 任何一門學(xué)科都有它的基礎(chǔ)和它的基本問題，如物質(zhì)的本質(zhì)是什么？有機(jī)體生命的基礎(chǔ)和起源是什么？ 什么是計(jì)算機(jī)科學(xué)的基礎(chǔ)？什么是計(jì)算機(jī)科學(xué)的基本問題？ 諸如什么是形式語言？什么是計(jì)算？什么是能計(jì)算的？什么是不能計(jì)算的？什么是算法？如何評價算法？什么樣的算法是可行的？這些問題能否判定？這又引出什么是可判定的？什么是不可判定的？ 這些問題就是計(jì)算理論要討論的問題。,性質(zhì)：該課是計(jì)算機(jī)科學(xué)的理論課。 計(jì)算理論：就是研究理論計(jì)算機(jī)的科學(xué)。 理論計(jì)算機(jī)：是研究計(jì)算機(jī)的理論模型，研究計(jì)算機(jī) 的本質(zhì)，也就是把計(jì)算機(jī)看成一個數(shù)學(xué)系統(tǒng)。(因?yàn)橛?jì)算 機(jī)科學(xué)的基本思想和模型在本質(zhì)上是數(shù)學(xué)離散的。) 內(nèi)容： 形式語言與自動機(jī)理論： 正規(guī)文法與有限自動機(jī)(正規(guī)語言) 、 上下文無關(guān)文法與下推自動機(jī)(上下文無關(guān)語言) 圖靈機(jī)(遞歸可枚舉語言) 可計(jì)算性理論： 什么是可計(jì)算？ 計(jì)算復(fù)雜性理論： 時間復(fù)雜性 、 空間復(fù)雜性。 遞歸函數(shù),二. 學(xué)習(xí)目的： 了解這些計(jì)算理論 我們知道計(jì)算機(jī)不論從它的誕生還是它的快速發(fā)展過程 都沒有離開計(jì)算理論，也就是它是在計(jì)算理論指導(dǎo)下誕生 和發(fā)展的。并課所涉及的都是計(jì)算機(jī)科學(xué)的基本問題。不 首先了解它們，是很難理解計(jì)算機(jī)科學(xué)的。作為計(jì)算機(jī)科 學(xué)與技術(shù)專業(yè)的本科生和研究生應(yīng)該了解這些計(jì)算理論。 培養(yǎng)能力 此外此課可以培養(yǎng)學(xué)生抽象邏輯思維和形式化思維的能 力。 為學(xué)習(xí)編譯原理做準(zhǔn)備,第一章,形式語言概述,語言是人們交流思想的工具。按照語言的形成，可將 語言分成二類：自然語言和人工語言（形式語言）。 一. 自然語言 如漢語、英語、法語、日語等等都是自然語言。 形成：是大多數(shù)人經(jīng)過長期地社會實(shí)踐逐漸形成的。 特點(diǎn)：種類繁多，內(nèi)容豐富，表達(dá)能力強(qiáng)。 缺點(diǎn)：具有地方性，不便互相交流。有時不夠精確， 有多義性。比如漢語中的“打”字，具有多種解釋。如打 傘、打撲克、打醋、打人、一打襪子等等。因此自然語 言不適合計(jì)算機(jī)的程序設(shè)計(jì)語言。 二.形式語言 如計(jì)算機(jī)的各種程序設(shè)計(jì)語言、數(shù)理邏輯中的謂詞演 算語言等都屬于形式語言。 形成：是少數(shù)人經(jīng)過嚴(yán)格地形式定義確定的語言。 特點(diǎn)：定義準(zhǔn)確，無歧義性。,在五十年代Chomky建立了形式語言的理論體系，從此 它發(fā)展很快，形式語言的研究已成為計(jì)算機(jī)科學(xué)的一個 重要領(lǐng)域。 形式語言：定義為一個嚴(yán)格的數(shù)學(xué)系統(tǒng)，其嚴(yán)格的形 式性使我們能給出形式語言的數(shù)學(xué)描述，進(jìn)而揭示所描 述語言的結(jié)構(gòu)、特性及其應(yīng)用范圍。 描述形式語言有兩種方法： 生成法 識別法。 生成法：用文法給出產(chǎn)生該語言的所有句子的規(guī)則。根 據(jù)這些規(guī)則可以產(chǎn)生語言中每個句子。這些規(guī)則就叫生 成式或產(chǎn)生式。,例如，下邊是個描述“十進(jìn)制數(shù)”的文法： G=(F,I,D,N, .,0,1,2,3,4,5,6,7,8,9, P, F) 令F“十進(jìn)制數(shù)”、 I“無符號整數(shù)”、 D“十進(jìn)制小數(shù)”、 N“數(shù)字” 于是該文法的產(chǎn)生式集合P中產(chǎn)生式如下： FI|D|ID IN|NI D.I N0|1|2|3|4|5|6|7|8|9 例如利用此文法產(chǎn)生3.14:,FIDND N.I3.I 3.NI3.1I 3.1N3.14,識別法：核心是一個自動機(jī)。對于給定的符號串可以 由自動機(jī)識別出是否為給定語言中合法的句子。 自動機(jī)的具體的例子以后再介紹。,1-1 形式語言基本概念,形式語言必須規(guī)定所用基本符號集合，這就是字母表。 一.字母表 字母表：符號的有限集合。通常用V或者表示。 例如 Va,b,c 。 二 符號串 符號串：是由字母表中的符號組成的序列。 例如，aabbcc就是上述字母表V上的一個符號串。 符號串的長度：即是符號串所含符號個數(shù)。 例如符號串a(chǎn)abbcc 用表示的長度，則 |6。 空符號串：不含任何符號的符號串，通常用表示。 顯然0 。,三.符號串的“連接”運(yùn)算“” 例符號串x=abc，y=cba，x與y的連接構(gòu)成符號串z, 則 z=xy=abccba=abccba 顯然連接運(yùn)算“”滿足可結(jié)合性且有幺元，即對任何符 號串x,y,z有 (xy)z=x(yz) x=x=x 對符號串的連接可以寫成乘冪的形式，即對任何符號串 x有： xx=x2 xxx=x3 一般地 xn-1x=xn xm xn =xm+n ( xm)n=xmn,四符號串集合的乘積 令A(yù)和B是符號串的集合，A與B的乘積記作AB，且 ABxyxAyB 例如，Aa,b,ab ，B=0,1 ， 則 ABa0,b0,ab0,a1,b1,ab1 由于符號串集合的乘積的運(yùn)算是可結(jié)合的，所以也可 寫成乘冪的形式。即A是符號串集合，則 AAA2 AmAn= Am+n (Am)n=Amn 當(dāng)兩個集合中有一個集合是空集時，則 它們的乘積為 空集。即A=A=。,五字母表的閉包V與V* 令V是個字母表。則 V由V中符號構(gòu)成的長度為1的符號串的集合。 V2由V中符號構(gòu)成的長度為2的符號串的集合。 V3由V中符號構(gòu)成的長度為3的符號串的集合。 于是 Vkw|w是由V中的符號構(gòu)成的符號串，且|w|=k V0= V=VV2V3V4 V*=V0VV2V3V4 V*是由V中符號構(gòu)成的任意長度的符號串(所有符號串)構(gòu)成的集合。,例如，V0,1 V+=0,1,00,01,10,11,000,001,010,011,100,101,110,111, V*=,0,1,00,01,10,11,000,001,010,011,100,101,110,111, 六語言 定義：設(shè)V是個字母表, LV*,則稱L是V上的一個語言。 例如，V0,1 L1= L2=0, 00, 000，0000，00000， L3=1, 11, 111, 1111, 11111, 上述 L1 、L2、L3 都是V上的語言。 七.句子 設(shè)L是V上的語言，如果w，則稱w是中的一個句子。 例如，000就是L2中的一個句子。,1.2 文法概念,文法是語言生成器中的最重要的一類，為了定義語言， 文法不僅作為一個“裝置”，給出語言的句子的結(jié)構(gòu)，而 且本身也是一個數(shù)學(xué)系統(tǒng)。 例如：前邊定義“十進(jìn)制數(shù)”的文法。 G=(F,I,D,N, .,0,1,2,3,4,5,6,7,8,9, P, F) F十進(jìn)制數(shù)、 I無符號整數(shù)、 D十進(jìn)制小數(shù)、N數(shù)字 于是該文法的產(chǎn)生式集合P中產(chǎn)生式如下： FI|D|ID IN|NI D.I N0|1|2|3|4|5|6|7|8|9 可見一個文法中有兩種符號。,1.文法（ Grammar）定義 一個文法G是個有序四元組，記作 =（,T ,），其中 非終極符(變元)集合，用大寫英文字母表示。 T 終極符集合。 這里 T =。有時記作 T 生成式(也叫產(chǎn)生式)的集合。 產(chǎn)生式的形式: ，其中 V，V * 的含義是：可以用符號串代替符號串。 另外如果有， 可簡記成 開始變元， 。,【例1-2.1】下面是定義只含有和*運(yùn)算的算術(shù) 表達(dá)式的文法。 =（ ,T ,） =,， ,+,*,(，) =， ， *， ， ()， ， 【例1-2.2】 =（S,0,1，P，S） P=S0S1|01,文法中使用的符號通常作如下約定： （1）用大寫英文字母表示變元。S通常表示開始變元。 （2）用小寫的a,b,c,表示終極符。 （3）用x,y,z,表示終極符串，即x,y,z,T*。 （4）用,希臘字母表示既含有終極符，也含有 非終極符的符號串，即,( T)*。 2.句型（Sentential form） 設(shè)文法 G =(,T ,S)，則 （1）S是個句型。 （2）若是個句型,且是中的一個產(chǎn)生式， 則也是一個句型。 按此定義，對于文法來說， PS0S1|01 S，0S1，00S11，000111都是句型。,3.句型的推導(dǎo)（派生） 設(shè)文法G=( ,T ,S)，若是G的一個句型， 且，則也是一個句型，我們就稱為可 由句型直接推導(dǎo)出,記作G。 如果沒有其它文法，不會產(chǎn)生混淆的情況下，此推導(dǎo)可 簡記成。 符號“”表示句型之間的直接推導(dǎo)(派生)關(guān)系。 如果有123n ，則表示由1可以間 接推導(dǎo)出n ，可以寫成1 * n , 符號“*”表示句型之間經(jīng)過多步間接推導(dǎo)的關(guān)系。 符號“k”表示句型之間經(jīng)過k步間接推導(dǎo)的關(guān)系。,4. 文法產(chǎn)生的語言 設(shè)文法 G =(,S)，令集合 L(G)=w|wT*且* w 則稱L(G)是由G產(chǎn)生的語言。 其中每個wL(G)是文法產(chǎn)生的句子。 在例1-2.2中，P=S0S1|01 有 S0S100S11000111, 所以L(G2)=0n1n|n1 【例1-2.3】 3 =(S,B,C,a,b,c，P，S) P: (1) SaSBC (2) SaBC (3) CBBC (4) aBab (5) bBbb (6) bCbc (7) cCcc,【例1-2.3】 3 =(S,B,C,a,b,c，P，S) P: (1) SaSBC (2) SaBC (3) CBBC (4) aBab (5) bBbb (6) bCbc (7) cCcc 求L(3)。 解. S *an-1S(BC)n-1 ( 產(chǎn)生式(1)使用n-1次) an(BC)n ( 產(chǎn)生式(2)使用一次) *an Bn Cn ( 產(chǎn)生式(3)使用多次) anbBn-1 Cn ( 產(chǎn)生式(4)使用一次) *an bn Cn ( 產(chǎn)生式(5)使用多次) an b ncCn-1 ( 產(chǎn)生式(6)使用一次) *an bn cn ( 產(chǎn)生式(7)使用多次) 所以 L(G3)=a n bn cn| n1,【例1-2.4】 4 =(S,A,B,a,b，P，S） P: SaB|bA , Aa|aS|bAA , Bb|bS|Abb 求證 L(4)中的每個句子里的a和b的個數(shù)相同。 證明：令Na(w)表示w中a的個數(shù)， L= w | wa,b+且Na(w)= Nb(w) 只要證明L(4)=L 即可。 1).先證 L(4)L 先用歸納法(對G中推導(dǎo)*的步數(shù)n作歸納)證明如 下結(jié)論： 如果 *，則 Na+A()=Nb+B()。 其中Na+A()表示中a和A的個數(shù)總和。,(1) 當(dāng)n=1時，此推導(dǎo)一定是用產(chǎn)生式 SaB|bA ，于是有 SaB 或 SbA 。 Na+A(aB)= Nb+B(bA) , 結(jié)論成立。 (2) 假設(shè)nk 時，結(jié)論成立。即如果有S n1 (表示從S 經(jīng)n步推出1)， 則 Na+A(1)= Nb+B(1) 。 (3) 當(dāng) n=k+1 時，不妨設(shè)k12 ，則由(2)得 Na+A(1)= Nb+B(1) 下面討論推導(dǎo)12 ，由于1中的變元只有三種， 所以分三種情況討論： 此派生是對1中的變元S作代換，必用產(chǎn)生式 SaB|bA ，顯然不論使用哪一個產(chǎn)生式，都能得出結(jié)論 Na+A(2)= Nb+B(2)。 此派生是對1中的變元A作代換，必用產(chǎn)生式 Aa|aS|bAA , 顯然不論使用哪一個產(chǎn)生式，都能得出結(jié) 論Na+A(2)= Nb+B(2)。, 此派生是對1中的變元B作代換，必用產(chǎn)生式 Bb|bS|Abb ，顯然不論使用哪一個產(chǎn)生式，都能得出 結(jié)論：Na+A(2)= Nb+B(2)。 綜上所述，上述命題成立。 任取wL(4)，于是有推導(dǎo)* w ,由上述結(jié)論得 Na+A()= Nb+B() 而在最后一步推導(dǎo)w中， 要消去中的變元，必 用產(chǎn)生式Aa或Bb ,顯然仍有Na+A(w)= Nb+B(w),此時w 中A和B的個數(shù)都為0，于是有Na(w)= Nb(w),所以wL， 于是有 L(4) L 。 2) 再證 L L(4) 任取wL ,顯然Na(w)= Nb(w),令Na(w)=n ,對n作歸納， 證出wL(4)。 (1) n=1 時，則w=ab,或w=ba，在4中有推導(dǎo)： SaBab或SbAba，所以有 wL(4),(2) 假設(shè)nk時，結(jié)論成立。即wL, Na(w)=Nb(w)， Na(w)k，則有wL(4)， 即4中有推導(dǎo)*w 。 (3) 當(dāng)n=k+1時，(即Na(w)= k+1,)，因?yàn)閣中的最左符號不 是a就是b。 下面分兩種情況討論。 a) w的最左符號是a ,不妨設(shè)w=aibx ,(i1), xa,b+, 如果i=1，w=abx , 則Na(x)=Nb(x),且 Na(x)=k ,由假設(shè)(2) 得 xL(4)， 所以 S*x ,于是有推導(dǎo)： SaBabS*abx =w , 所以wL(4)。 如果i1, w=aibx，可將w寫成w=aibw1bw2bwi，其中 Na(wj)=Nb(wj) (1ji), 這些wj中，可能wj=或wjL。 如果wjL，又Na(wj)k，由歸納假設(shè)得wjL(4)， 即S*wj 于是在4中有推導(dǎo)： SaBaaBB*aiBi , 再往下推導(dǎo)。,SaBaaBB*aiBi , 再往下推導(dǎo)。 如果wj=，則對應(yīng)的第j個B可用產(chǎn)生式Bb替換，可 得Bbwj。 如果 wj,則對應(yīng)得第j 個B可用產(chǎn)生式BbS替換， 又因?yàn)镾 * wj,可得B *bwj，最后得推導(dǎo)： SaBaaBB*aiBi*aibw1Bi-1* aibw1bw2Bi-2 * aibw1 bw2bw3bwi=w 即有 S*w , wL(4) 。 b) 當(dāng)w的最左符號是b時，不妨設(shè)w=biax (i1), xa,b+，類似可證。 于是，對于n=k+1 時，命題成立。 即，如果wL，則wL(4),所以 LL(4)。 最后得，L=L(4)=w|wa,b+且Na(w)= Nb(w)。,1-3 文法的分類,按照文法的產(chǎn)生式的結(jié)構(gòu)不同，將文法分成四類，稱之為Chomsky分類。 分別稱之為0型、1型、2型、3型。 令文法 G =(,S) T, 具體的結(jié)構(gòu)形式如下表所示：,類型 文 法 結(jié) 構(gòu) 產(chǎn) 生 式 形 式 限 制 條 件,0 短語結(jié)構(gòu)文法 +,* Phrase Structure,上下文有關(guān)文法 1A212 |12|1A2| 1 Context Sensitive 1，2* （CSG ） A , +,上下文無關(guān)文法 A A,* 2 Context Free （CFG）,正 右線性文法 AxB，Cy A,B,C 3 規(guī) 文 左線性文法 ABx，Cy x,yT* 法,按照此定義，判定上一節(jié)給定的四個文法是何類型： =( ,T ,) =,， ,+,*,(，) =， *， ()， ， =(S,0,1，P，S) P=S0S1|01 3 =(S,B,C,a,b,c，P，S) P: (1) SaSBC (2) SaBC (3) CBBC (4) aBab (5) bBbb (6) bCbc (7) cCcc 4=(S,A,B,a,b，P，S） P: SaB|bA ,