計算理論第一章

計算理論課件第一章第一頁，共三十一頁，2022年，8月28日序言一.本課的性質(zhì)以及研究的內(nèi)容任何一門學科都有它的基礎(chǔ)和它的基本問題，如物質(zhì)的本質(zhì)是什么？有機體生命的基礎(chǔ)和起源是什么？什么是計算機科學的基礎(chǔ)？什么是計算機科學的基本問題？諸如什么是形式語言？什么是計算？什么是能計算的？什么是不能計算的？什么是算法？如何評價算法？什么樣的算法是可行的？這些問題能否判定？這又引出什么是可判定的？什么是不可判定的？這些問題就是計算理論要討論的問題。第二頁，共三十一頁，2022年，8月28日性質(zhì)：該課是計算機科學的理論課。計算理論：就是研究理論計算機的科學。理論計算機：是研究計算機的理論模型，研究計算機的本質(zhì)，也就是把計算機看成一個數(shù)學系統(tǒng)。(因為計算機科學的基本思想和模型在本質(zhì)上是數(shù)學——離散的。)內(nèi)容：形式語言與自動機理論：正規(guī)文法與有限自動機(正規(guī)語言)、上下文無關(guān)文法與下推自動機(上下文無關(guān)語言)

圖靈機(遞歸可枚舉語言)可計算性理論：什么是可計算？計算復(fù)雜性理論：時間復(fù)雜性、空間復(fù)雜性。遞歸函數(shù)第三頁，共三十一頁，2022年，8月28日二.學習目的：了解這些計算理論我們知道計算機不論從它的誕生還是它的快速發(fā)展過程都沒有離開計算理論，也就是它是在計算理論指導(dǎo)下誕生和發(fā)展的。并課所涉及的都是計算機科學的基本問題。不首先了解它們，是很難理解計算機科學的。作為計算機科學與技術(shù)專業(yè)的本科生和研究生應(yīng)該了解這些計算理論。培養(yǎng)能力此外此課可以培養(yǎng)學生抽象邏輯思維和形式化思維的能力。為學習《編譯原理》做準備第四頁，共三十一頁，2022年，8月28日第一章形式語言概述第五頁，共三十一頁，2022年，8月28日

語言是人們交流思想的工具。按照語言的形成，可將語言分成二類：自然語言和人工語言（形式語言）。一.自然語言

如漢語、英語、法語、日語等等都是自然語言。

形成：是大多數(shù)人經(jīng)過長期地社會實踐逐漸形成的。

特點：種類繁多，內(nèi)容豐富，表達能力強。缺點：具有地方性，不便互相交流。有時不夠精確，有多義性。比如漢語中的“打”字，具有多種解釋。如打傘、打撲克、打醋、打人、一打襪子等等。因此自然語言不適合計算機的程序設(shè)計語言。二.形式語言如計算機的各種程序設(shè)計語言、數(shù)理邏輯中的謂詞演算語言等都屬于形式語言。

形成：是少數(shù)人經(jīng)過嚴格地形式定義確定的語言。特點：定義準確，無歧義性。第六頁，共三十一頁，2022年，8月28日在五十年代Chomky建立了形式語言的理論體系，從此它發(fā)展很快，形式語言的研究已成為計算機科學的一個重要領(lǐng)域。

形式語言：定義為一個嚴格的數(shù)學系統(tǒng)，其嚴格的形式性使我們能給出形式語言的數(shù)學描述，進而揭示所描述語言的結(jié)構(gòu)、特性及其應(yīng)用范圍。

描述形式語言有兩種方法：生成法識別法。生成法：用文法給出產(chǎn)生該語言的所有句子的規(guī)則。根據(jù)這些規(guī)則可以產(chǎn)生語言中每個句子。這些規(guī)則就叫生成式或產(chǎn)生式。

第七頁，共三十一頁，2022年，8月28日例如，下邊是個描述“十進制數(shù)”的文法：

G=({F,I,D,N},{.,0,1,2,3,4,5,6,7,8,9},P,F)令F——“十進制數(shù)”、I——“無符號整數(shù)”、

D——“十進制小數(shù)”、N——“數(shù)字”于是該文法的產(chǎn)生式集合P中產(chǎn)生式如下：

F→I|D|IDI→N|NID→.IN→0|1|2|3|4|5|6|7|8|9例如利用此文法產(chǎn)生3.14:FIDNDN.I3.I3.NI3.1I3.1N3.14識別法：核心是一個自動機。對于給定的符號串可以由自動機識別出是否為給定語言中合法的句子。自動機的具體的例子以后再介紹。第八頁，共三十一頁，2022年，8月28日1-1

形式語言基本概念形式語言必須規(guī)定所用基本符號集合，這就是字母表。一.字母表字母表：符號的有限集合。通常用V或者表示。例如V＝a,b,c

。二．

符號串符號串：是由字母表中的符號組成的序列。例如，aabbcc就是上述字母表V上的一個符號串。符號串的長度：即是符號串所含符號個數(shù)。例如符號串＝aabbcc用表示的長度，則|＝6?？辗柎翰缓魏畏柕姆柎ǔＳ帽硎?。顯然＝0。第九頁，共三十一頁，2022年，8月28日三.符號串的“連接”運算“?”例符號串x=abc，y=cba，x與y的連接構(gòu)成符號串z,則

z=x?y=abc?cba=abccba

顯然連接運算“?”滿足可結(jié)合性且有幺元，即對任何符號串x,y,z有

(x?y)?z=x?(y?z)x?=?x=x

對符號串的連接可以寫成乘冪的形式，即對任何符號串x有：

x?x=x2x?x?x=x3一般地

xn-1?x=xnxm?xn=xm+n

(

xm)n=xmn第十頁，共三十一頁，2022年，8月28日四．符號串集合的乘積令A(yù)和B是符號串的集合，A與B的乘積記作AB，且

AB＝x?yxAyB例如，A＝a,b,ab

，B=0,1

，則

AB＝a0,b0,,ab0,a1,b1,ab1

由于符號串集合的乘積的運算是可結(jié)合的，所以也可寫成乘冪的形式。即A是符號串集合，則

AA＝A2AmAn=

Am+n(Am)n=Amn

當兩個集合中有一個集合是空集時，則它們的乘積為空集。即A=A=。第十一頁，共三十一頁，2022年，8月28日五．字母表的閉包V與V*

令V是個字母表。則

V——由V中符號構(gòu)成的長度為1的符號串的集合。

V2——由V中符號構(gòu)成的長度為2的符號串的集合。

V3——由V中符號構(gòu)成的長度為3的符號串的集合。于是

Vk＝{w|w是由V中的符號構(gòu)成的符號串，且|w|=k}V0={}V=VV2V3V4…V*=V0VV2V3V4…V*是由V中符號構(gòu)成的任意長度的符號串(所有符號串)構(gòu)成的集合。第十二頁，共三十一頁，2022年，8月28日例如，V＝{0,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上的一個語言。例如，V＝{0,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中的一個句子。第十三頁，共三十一頁，2022年，8月28日1.2文法概念

文法是語言生成器中的最重要的一類，為了定義語言，文法不僅作為一個“裝置”，給出語言的句子的結(jié)構(gòu)，而且本身也是一個數(shù)學系統(tǒng)。例如：前邊定義“十進制數(shù)”的文法。

G=({F,I,D,N},{.,0,1,2,3,4,5,6,7,8,9},P,F)F—十進制數(shù)、I—無符號整數(shù)、

D—十進制小數(shù)、N—數(shù)字于是該文法的產(chǎn)生式集合P中產(chǎn)生式如下：

F→I|D|IDI→N|NID→.IN→0|1|2|3|4|5|6|7|8|9可見一個文法中有兩種符號。非終極符終極符第十四頁，共三十一頁，2022年，8月28日1.文法（Grammar）定義一個文法G是個有序四元組，記作Ｇ=（ＶＮ,ＶT,Ｐ,Ｓ），其中

ＶＮ非終極符(變元)集合，用大寫英文字母表示。

ＶT

終極符集合。這里ＶＮ∩ＶT=Ф。有時記作ＶＮ∪ＶT＝Ｖ

Ｐ生成式(也叫產(chǎn)生式)的集合。產(chǎn)生式的形式:α→β，其中α∈V，β∈V*α→β的含義是：可以用符號串β代替符號串α。另外如果有α→β，α→γ，α→δ

可簡記成α→β｜γ｜δ

Ｓ開始變元，Ｓ∈ＶＮ。第十五頁，共三十一頁，2022年，8月28日【例1-2.1】下面是定義只含有＋和*運算的算術(shù)表達式的文法。Ｇ１=（ＶＮ,ＶT,Ｐ,Ｅ）ＶＮ=｛Ｅ,Ｔ,Ｆ｝，ＶＴ＝｛ａ,ｂ,+,*,(，)｝Ｐ={Ｅ→Ｅ＋Ｔ，Ｅ→Ｔ，Ｔ→Ｔ*Ｆ，Ｔ→Ｆ，Ｆ→(Ｅ)，Ｆ→ａ，Ｆ→ｂ}【例1-2.2】

Ｇ２=（{S},{0,1}，P，S）

P={S→0S1|01}第十六頁，共三十一頁，2022年，8月28日文法中使用的符號通常作如下約定：（1）用大寫英文字母表示變元。S通常表示開始變元。（2）用小寫的a,b,c,…表示終極符。（3）用x,y,z,…表示終極符串，即x,y,z,…∈ＶT*。（4）用α,β,γ,…希臘字母表示既含有終極符，也含有非終極符的符號串，即α,β,γ,…∈(ＶＮ∪ＶT)*。2.句型（Sententialform）設(shè)文法G=(ＶＮ,ＶT,Ｐ,S)，則（1）S是個句型。（2）若αβγ是個句型,且β→δ是Ｐ中的一個產(chǎn)生式，則αδγ也是一個句型。按此定義，對于文法Ｇ２來說，P＝{S→0S1|01}S，0S1，00S11，000111都是句型。第十七頁，共三十一頁，2022年，8月28日3.句型的推導(dǎo)（派生）設(shè)文法G=(ＶＮ,ＶT,Ｐ,S)，若αβγ是G的一個句型，且β→δ∈Ｐ，則αδγ也是一個句型，我們就稱為可由句型αβγ直接推導(dǎo)出αδγ,記作αβγGαδγ。如果沒有其它文法，不會產(chǎn)生混淆的情況下，此推導(dǎo)可簡記成αβγαδγ。符號“”表示句型之間的直接推導(dǎo)(派生)關(guān)系。如果有α1α2α3…αn，則表示由α1可以間接推導(dǎo)出αn，可以寫成α1*

αn,

符號“*”表示句型之間經(jīng)過多步間接推導(dǎo)的關(guān)系。符號“k”表示句型之間經(jīng)過k步間接推導(dǎo)的關(guān)系。第十八頁，共三十一頁，2022年，8月28日4.文法產(chǎn)生的語言設(shè)文法G=(ＶＮ,ＶＴ,Ｐ,S)，令集合

L(G)={w|w∈ＶT*且Ｓ*

w}則稱L(G)是由G產(chǎn)生的語言。其中每個w∈L(G)是文法Ｇ產(chǎn)生的句子。在例1-2.2中，P={S→0S1|01}

有S0S100S11000111,所以L(G2)={0n1n|n≥1}【例1-2.3】

Ｇ3=({S,B,C},{a,b,c}，P，S)P:(1)S→aSBC(2)S→aBC(3)CB→BC(4)aB→ab(5)bB→bb(6)bC→bc(7)cC→cc第十九頁，共三十一頁，2022年，8月28日【例1-2.3】

Ｇ3=({S,B,C},{a,b,c}，P，S)P:(1)S→aSBC(2)S→aBC(3)CB→BC(4)aB→ab(5)bB→bb(6)bC→bc(7)cC→cc求L(Ｇ3)。解.S*an-1S(BC)n-1(產(chǎn)生式(1)使用n-1次)an(BC)n(產(chǎn)生式(2)使用一次)*anBnCn(產(chǎn)生式(3)使用多次)anbBn-1Cn(產(chǎn)生式(4)使用一次)*anbnCn(產(chǎn)生式(5)使用多次)anbncCn-1(產(chǎn)生式(6)使用一次)*anbncn(產(chǎn)生式(7)使用多次)所以L(G3)={anbncn|n≥1}第二十頁，共三十一頁，2022年，8月28日【例1-2.4】

Ｇ4=({S,A,B},{a,b}，P，S）

P:S→aB|bA,A→a|aS|bAA,B→b|bS|Abb求證L(Ｇ4)中的每個句子里的a和b的個數(shù)相同。證明：令Na(w)表示w中a的個數(shù)，

L={w|w∈{a,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ù)總和。第二十一頁，共三十一頁，2022年，8月28日(1)

當n=1時，此推導(dǎo)一定是用產(chǎn)生式S→aB|bA，于是有

SaB或SbA。Na+A(aB)=Nb+B(bA),結(jié)論成立。(2)假設(shè)n≤k時，結(jié)論成立。即如果有Snα1(表示從S

經(jīng)n步推出α1)，則Na+A(α1)=Nb+B(α1)。(3)

當n=k+1時，不妨設(shè)Ｓkα1α2，則由(2)得

Na+A(α1)=Nb+B(α1)

下面討論推導(dǎo)α1α2，由于α1中的變元只有三種，所以分三種情況討論：

①此派生是對α1中的變元S作代換，必用產(chǎn)生式S→aB|bA，顯然不論使用哪一個產(chǎn)生式，都能得出結(jié)論Na+A(α2)=Nb+B(α2)。

②此派生是對α1中的變元A作代換，必用產(chǎn)生式A→a|aS|bAA,顯然不論使用哪一個產(chǎn)生式，都能得出結(jié)論Na+A(α2)=Nb+B(α2)。第二十二頁，共三十一頁，2022年，8月28日③此派生是對α1中的變元B作代換，必用產(chǎn)生式B→b|bS|Abb，顯然不論使用哪一個產(chǎn)生式，都能得出結(jié)論：Na+A(α2)=Nb+B(α2)。

綜上所述，上述命題成立。任取w∈L(Ｇ4)，于是有推導(dǎo)Ｓ*αw,由上述結(jié)論得Na+A(α)=Nb+B(α)

而在最后一步推導(dǎo)αw中，要消去α中的變元，必用產(chǎn)生式A→a或B→b,顯然仍有Na+A(w)=Nb+B(w),此時w中A和B的個數(shù)都為0，于是有Na(w)=Nb(w),所以w∈L，于是有L(Ｇ4)L

。2)再證LL(Ｇ4)

任取w∈L,顯然Na(w)=Nb(w),令Na(w)=n,對n作歸納，證出w∈L(Ｇ4)。

(1)n=1時，則w=ab,或w=ba，在Ｇ4中有推導(dǎo)：

SaBab或SbAba，所以有w∈L(Ｇ4)第二十三頁，共三十一頁，2022年，8月28日(2)

假設(shè)n≤k時，結(jié)論成立。即w∈L,Na(w)=Nb(w)，Na(w)≤k，則有w∈L(Ｇ4)，即Ｇ4中有推導(dǎo)Ｓ*w。(3)

當n=k+1時，(即Na(w)=k+1,)，因為w中的最左符號不是a就是b。下面分兩種情況討論。

a)w的最左符號是a,不妨設(shè)w=aibx,(i≥1),x∈{a,b}+,

如果i=1，w=abx,則Na(x)=Nb(x),且Na(x)=k,由假設(shè)(2)得x∈L(Ｇ4)，所以S*x,于是有推導(dǎo)：

SaBabS*abx=w,所以w∈L(Ｇ4)。如果i>1,w=aibx，可將w寫成w=aibw1bw2…bwi，其中

Na(wj)=Nb(wj)(1≤j≤i),這些wj中，可能wj=ε或wj∈L。如果wj∈L，又Na(wj)≤k，由歸納假設(shè)得wj∈L(Ｇ4)，即S*wj于是在Ｇ4中有推導(dǎo)：

SaBaaBB*aiBi,再往下推導(dǎo)。第二十四頁，共三十一頁，2022年，8月28日

SaBaaBB*aiBi,再往下推導(dǎo)。如果wj=ε，則對應(yīng)的第j個B可用產(chǎn)生式B→b替換，可得Bbwj。如果wj≠ε,則對應(yīng)得第j個B可用產(chǎn)生式B→bS替換，又因為S*

wj,可得B*bwj，最后得推導(dǎo)：

SaBaaBB*aiBi*aibw1Bi-1*

aibw1bw2Bi-2*…*

aibw1bw2bw3…bwi=w

即有S*w,w∈L(Ｇ4)。

b)當w的最左符號是b時，不妨設(shè)w=biax(i≥1),x∈{a,b}+，類似可證。于是，對于n=k+1時，命題成立。即，如果w∈L，則w∈L(Ｇ4),所以LL(Ｇ4)。最后得，L=L(Ｇ4)={w|w∈{a,b}+且Na(w)=Nb(w)}。

第二十五頁，共三十一頁，2022年，8月28日1-3文法的分類按照文法的產(chǎn)生式的結(jié)構(gòu)不同，將文法分成四類，稱之為Chomsky分類。分別稱之為0型、1型、2型、3型。令文法G=(ＶＮ,ＶＴ,Ｐ,S)ＶＮ∪ＶT＝Ｖ,

具體的結(jié)構(gòu)形式如下表所示：第二十六頁，共三十一頁，2022年，8月28日類型文法結(jié)構(gòu)產(chǎn)生式形式限制條件

0短語結(jié)構(gòu)文法α→βα∈Ｖ+,β∈Ｖ*

PhraseStructure上下文有關(guān)文法α1Aα2→α1βα2|α1βα2|≥|α1Aα2|

1ContextSensitiveα1，α2∈Ｖ*（CSG）A∈ＶＮ,β∈Ｖ+上下文無關(guān)文法A→αA∈ＶＮ,α∈Ｖ*2ContextFree（CFG）正右線性文法A→xB，C→yA,B,C∈ＶＮ

3

規(guī)文左線性文法A→Bx，C→y

x,y∈ＶT*法第二十七頁，共三十一頁，2022年，8月28日按照此定義，判定上一節(jié)給定的四個文法是何類型：Ｇ１=(ＶＮ,ＶT,Ｐ,Ｅ)

ＶＮ={Ｅ,Ｔ,Ｆ}，ＶＴ＝{ａ,ｂ,+,*,(，)}

Ｐ={Ｅ→Ｅ＋Ｔ，Ｅ→Ｔ，Ｔ→Ｔ*Ｆ，Ｔ→Ｆ，Ｆ→(Ｅ)，Ｆ→ａ，Ｆ→ｂ}Ｇ２=({S},{0,1}，P，S)P={S→0S1|01}Ｇ3=({S,B,C},{a,b,c}，P，S)P:(1)S→aSBC(2)S→aBC(3)CB→BC(4)aB→ab(5)b