計算機(jī)數(shù)學(xué)基礎(chǔ)PPT課件

1、2021/3/91計算機(jī)科學(xué)的數(shù)學(xué)基礎(chǔ)第一章：語言與第一章：語言與正規(guī)語言正規(guī)語言1.1 符號、符號串及其運算符號、符號串及其運算符號和符號串在形式語言中是非常重要的基本概念。在計算機(jī)科學(xué)的發(fā)展中，符號主義一直占據(jù)著非常重要的位置。語言的基礎(chǔ)是字母表。王雷版權(quán)所有2021/3/921.1 符號、符號串及其運算符號、符號串及其運算字母表：字母表：一個非空的有限集合稱為字母表，通常用或者大寫的西文字母表示。字母表中的元素稱作為字母或符號，一般用小寫字母、數(shù)字等表示。符號串：符號串：一個符號串是由字母表中的字母組成的一個有限序列。符號串的長度：符號串的長度：符號串所包含符號的個數(shù)稱為符號串的長度。符

2、號串w的長度記為|w|?？沾嚎沾洪L度為0的符號串稱為空串，用表示。王雷版權(quán)所有2021/3/931.1 符號、符號串及其運算符號、符號串及其運算符號串的聯(lián)結(jié)符號串的聯(lián)結(jié)：聯(lián)結(jié)是符號串的基本運算。兩個符號串X和Y的聯(lián)結(jié)，記為XY，就是把Y跟隨在X的后面形成的符號串。例例1.1：設(shè) = 1, 2是一個字母表。設(shè)X = 11、Y = 22分別是上的兩個符號串。則： XY = 1122是X、Y兩個符號串的聯(lián)結(jié)，XY是上的一符號串。 YX = 2211是Y、X兩個符號串的聯(lián)結(jié)，YX也是上的一符號串。一般來說，符號串的聯(lián)結(jié)不滿足交換律。顯然符號串的聯(lián)結(jié)是滿足結(jié)合律的，即有，(XY)Z = X(YZ)。

3、在例1.1中，顯然有XYYX，(XY)X = X(YX) = 112211。王雷版權(quán)所有2021/3/941.1 符號、符號串及其運算符號、符號串及其運算由于是不含符號的符號串(空串)，所以對任意符號串X都有，X = X = X。由此我們可以認(rèn)為是符號串聯(lián)結(jié)運算的單位元。符號串的方冪符號串的方冪：設(shè)X是符號串，把X自身聯(lián)結(jié)n次后，得到的符號串Z，即Z = XXXX = Xn，稱為X的方冪。我們約定X0 = 。這個定義可以遞歸地表示為：100nnnXXXn王雷版權(quán)所有2021/3/951.1 符號、符號串及其運算符號、符號串及其運算符號串的子串、前綴符號串的子串、前綴和后綴：和后綴： 符號串V是

4、符號串W的子串，當(dāng)且僅當(dāng)存在符號串X和Y，使得W = XVY。這里，X和Y都可能是空串。集合的聯(lián)結(jié)：集合的聯(lián)結(jié)：設(shè)A和B都是符號串的集合，定以集合A和B的聯(lián)結(jié)為：AB = XY | XA且YB，即集合A和B的聯(lián)結(jié)是集合A中的符號串和集合B中的符號串的聯(lián)結(jié)所構(gòu)成的集合。 王雷版權(quán)所有2021/3/961.1 符號、符號串及其運算符號、符號串及其運算集合的方冪集合的方冪：設(shè)A是符號串的集合，把A自身聯(lián)結(jié)n次后，得到的新的集合An，即An = AAA，稱為集合A的方冪。我們約定A0 = 。這個定義可以遞歸地表示為：1 00nnnAA An王雷版權(quán)所有2021/3/971.1 符號、符號串及其運算符號

5、、符號串及其運算集合的閉包和正閉包集合的閉包和正閉包：設(shè)A是符號串的集合，用A*表示A的所有的有限次方冪的并集，則稱A*為集合A上的閉包，即：注意：閉包A*與正閉包A+的差別在于是否包含空串。在閉包A*中去掉空串后就成為正閉包A+。A* 具有可數(shù)無窮多的符號串。A* = A0A1A2An而稱A+ = A1A2An 為A上的正閉包，顯然,有A* = A0 A+ ， A+ = A*A = AA*。語言：語言：令為一個字母表。若L *，則L是字母表上的一個語言。 即：L為一個由字母表上的字符串所構(gòu)成的集合。王雷版權(quán)所有2021/3/981.2 文法與語言的形式定義文法與語言的形式定義語言都是用文法來

6、描述的。一個文法實際上是一組有限的規(guī)則式。非終結(jié)符（非終結(jié)符（一種過渡性符一種過渡性符號號）：也是一種符號，但不是字母表中的符號。我們將它記為V。終結(jié)符終結(jié)符：是一個語言的字母表中的符號。我們將它記為T。對于一個形式語言L，設(shè)T和V分別是它的終結(jié)符集和非終結(jié)符集，顯然有L T*，且TV = 。王雷版權(quán)所有2021/3/991. 2. 1 文法的形式化定義文法的形式化定義定義定義1. 1：一條產(chǎn)生式是一個有序?qū)?, ), 通?？蓪懽魅缦滦问?= 或 其中：V+，V*，V= VT 。稱為產(chǎn)生式的左部，稱為產(chǎn)生式的右部。注意： V+說明是一個非終結(jié)符且，即產(chǎn)生式的左部不允許是空串。 V*說明產(chǎn)生式的

7、右部是這樣的一個符號串，它可以含有終結(jié)符，也可以含有非終結(jié)符，同時還可以為空串。王雷版權(quán)所有2021/3/9101. 2. 1 文法的形式化定義文法的形式化定義定義定義1. 2：文法G定義為一個四元組G = (V，T，P，S), 其中：1、V是一個非空的有窮集合，稱為非終結(jié)符集。2、T是一個非空的有窮集合，稱為終結(jié)符集，且VT = 。3、P是一個非空的有窮的產(chǎn)生式的集合。4、SV，稱為文法的開始符號，S至少要在P中的一條產(chǎn)生式中作為左部出現(xiàn)。 王雷版權(quán)所有2021/3/9111. 2. 1 文法的形式化定義文法的形式化定義例例1.2 設(shè)文法G = (A, E，a，P，A)，其中P = Aa，A

8、aE，EaA。在許多的文法中，有多條產(chǎn)生式的左部相同，可以將左部相同的產(chǎn)生式寫成合并的產(chǎn)生式形式。在此例文法G中，P中的前兩個產(chǎn)生式的左部相同，都是A，可以合并為A a | aE，這樣一來，P = A a | aE，EaA。在許多情況下，只需要將文法的產(chǎn)生式寫出就可以表明該文法了。約定：第一條產(chǎn)生式的左部是文法的開始符 王雷版權(quán)所有2021/3/9121. 2. 2 推導(dǎo)的形式化定義推導(dǎo)的形式化定義定義定義1. 3：給定一個文法G = (V, T, P, S)，如果是G中的一條產(chǎn)生式，和是V*中的任意符號，若存在符號串x, y滿足：x = ，y = ，則稱x使用了產(chǎn)生式直接產(chǎn)生了y，或者稱y是

9、x的直接推導(dǎo)，或者稱y可以直接歸約到x，記作x y。例：令x = aAb，y = acb， = a， = b，則y是x的直接推導(dǎo)，即：aAb acb，所使用的產(chǎn)生式為Ac。王雷版權(quán)所有2021/3/9131. 2. 2 推導(dǎo)的形式化定義推導(dǎo)的形式化定義定義定義1. 4：給定一個文法G = (V, T, P, S)，設(shè)x，yV*，如果： 1、存在如下的直接推導(dǎo)序列：x = w0 w1 w2 wn = y(n0)則稱x推導(dǎo)出(產(chǎn)生)y，推導(dǎo)長度為n，或者稱為y歸約到x，記作x n y。 2、 我們用x+y表示存在n0且x n y； 用x*y表示有x + y或者x = y。最左最左(右右)推導(dǎo)推導(dǎo)：

10、如果在推導(dǎo)的每一步x y，都是對x中的最左(右)邊的非終結(jié)符選用產(chǎn)生式進(jìn)行替換，則這種推導(dǎo)稱為最左(右)推導(dǎo)。最右推導(dǎo)也稱為規(guī)規(guī)范推導(dǎo)范推導(dǎo)。王雷版權(quán)所有2021/3/9141. 2. 2 推導(dǎo)的形式化定義推導(dǎo)的形式化定義規(guī)范句型、規(guī)范句型、短語短語、直直接短語接短語和句柄句柄定義定義1. 5：給定一個文法G = (V, T, P, S)，如果符號串x是從文法G的開始符號S推導(dǎo)出來的，即S *x，則稱x是文法G的句型。如果符號串x是僅由終結(jié)符組成的句型，即S*x且xT*，則稱x是文法G的句子。由規(guī)范推導(dǎo)所得到的句型就稱之為規(guī)范句型規(guī)范句型。 王雷版權(quán)所有2021/3/9151. 2. 2 推導(dǎo)

11、的形式化定義推導(dǎo)的形式化定義規(guī)范句型、規(guī)范句型、短語短語、直直接短語接短語和句柄句柄定義定義1. 6 設(shè)GS是一文法，x = w是一句型，如果：S*A且A * w則稱w是句型x的一個相對于非終結(jié)符A的短語；如果：S*A且Aw則稱w是句型x的一個相對于非終結(jié)符的直接短語(或簡單短語)；如果w是一個句型x的最左直接短語，稱w為句型x的句柄。王雷版權(quán)所有2021/3/9161.2.3 語言的形式化定義語言的形式化定義定義定義1.7：給定一個文法G = (V, T, P, S)，由G所生成的語言記作L(G)，令L(G) = x | S+x且xT*，其中x稱為語言L(G)的句子。即： L(G)是一個由從

12、文法G的開始符號S所推導(dǎo)出來的所有句子所構(gòu)成的集合。例例1.3 給定文法GS：S aSb | ab 由該文法生成的任何一個句子都是： 先使用產(chǎn)生式SaSb若干次得到：S aSb aaSbb an-1S bn-1 ，即S+ an-1S bn-1 ；再使用產(chǎn)生式S ab一次得到：S+ an-1S bn-1 anbn。不難對推導(dǎo)的步數(shù)用數(shù)學(xué)歸納法證明該文法推導(dǎo)的所有符號串都是anbn的形式。另一方面，我們也不難對符號串的長度用數(shù)學(xué)歸納法證明，對任何形式為anbn，n1，的符號串，一定可以用文法GS推導(dǎo)出來，即存在推導(dǎo)S+ anbn。所以，L(GS) = anbn | n1。 王雷版權(quán)所有2021/3

13、/9171.2.3 語言的形式化定義語言的形式化定義例例1.4 設(shè)文法GV：V aVb，Vb bW，abW c。求文法GV所生成的語言。解：V是文法的開始符。繼續(xù)多次使用該產(chǎn)生式，得到的推導(dǎo)結(jié)果是：anVbn，n1。在anVbn中，為了消除非終結(jié)符V，必須使用產(chǎn)生式VbbW，得到推導(dǎo)結(jié)果是：anbWbn-1 = an-1abWbn-1，n1。只有使用產(chǎn)生式abWc，才能消除非終結(jié)符W，最終得到推導(dǎo)結(jié)果：an-1cbn-1，n1。另一方面，不難證明，對任何形式為ancbn，n0的符號串都可以用文法GV推導(dǎo)出來。因此，文法GV生成的語言為：L(GV) = an-1cbn-1 | n1 = ancb

14、n | n0。王雷版權(quán)所有2021/3/9181.2.3 語言的形式化定義語言的形式化定義例例1.5 文法GA：AaR，Aab，RAb所生成的語言L(GA) = anbn | n1。(留做課后習(xí)題)。 從上面可以看出，盡管文法GA與例1.7中的文法GS是兩個不同的文法，但是所生成的語言是相同，都是anbn | n 1。定義定義1.8 給定任意兩個文法G1、G2，如果它們所生成語言相同，即：L(G1) = L(G2)，則稱文法G1與G2是等價的。王雷版權(quán)所有2021/3/9191.2.4 語法樹語法樹語法樹是句型推導(dǎo)過程的圖形表示。 例如，設(shè)句子bd0的最右推導(dǎo)或規(guī)范推導(dǎo)為： 0 0 d0 d0

15、 bd0王雷版權(quán)所有bd0圖圖1.2 句子句子bd0的語法樹的語法樹2021/3/9201.2.4 語法樹語法樹定義定義1.9 如果一個文法存在某個句子對應(yīng)兩棵以上的不同的語法樹，或有兩個以上的不同的最左(右)推導(dǎo)，則稱該文法是二二義性文法（程序設(shè)計義性文法（程序設(shè)計語言不能有二義性語言不能有二義性 ）。定義定義1.10 如果一個語言L的任何文法都是二義性文法，則稱該語言L是二義性語言。在理論上已經(jīng)證明了，存在著這種二義性的語言。 文法的二義性與語言的二義性是兩個不同的概念。王雷版權(quán)所有2021/3/9211.2.5 文法和語言的類型文法和語言的類型Chomsky于1956年把文法分成四種類型

16、，即：0型文法、1型文法、2型文法和3型文法。這種文法的分類稱作Chomsky分類。文法所生成的語言，根據(jù)四種類型文法，也分為四種，即：0型語言、1型語言、2型語言和3型語言。Chomsky建立的形式語言理論對計算機(jī)科學(xué)的發(fā)展規(guī)律有著深刻的影響，特別是對計算機(jī)程序設(shè)計語言的設(shè)計、編譯方法和計算復(fù)雜性等方面具有更大的作用。王雷版權(quán)所有諾姆諾姆喬姆斯基（喬姆斯基（Noam Chomsky, 1928-），美國），美國語言學(xué)語言學(xué)家，轉(zhuǎn)換家，轉(zhuǎn)換-生成語法的創(chuàng)始人。生成語法的創(chuàng)始人。1928年年12月月7日出生于美國日出生于美國賓夕法尼亞州賓夕法尼亞州的的費城費城。1947年，在年，在哈里斯哈里斯的

17、影響下他開始的影響下他開始研究語言學(xué)。研究語言學(xué)。1951年在賓夕法尼亞大學(xué)完成碩士論文年在賓夕法尼亞大學(xué)完成碩士論文現(xiàn)現(xiàn)代希伯萊語語素音位學(xué)代希伯萊語語素音位學(xué)，1955年在該校完成博士論文年在該校完成博士論文轉(zhuǎn)換分析轉(zhuǎn)換分析，獲得博士學(xué)位。從，獲得博士學(xué)位。從1955年秋天開始，他一年秋天開始，他一直在直在麻省理工學(xué)院麻省理工學(xué)院工作，曾任該校語言學(xué)與哲學(xué)系主任，并工作，曾任該校語言學(xué)與哲學(xué)系主任，并任該校認(rèn)知科學(xué)研究中心主任，為語言學(xué)界培養(yǎng)了一批有素任該校認(rèn)知科學(xué)研究中心主任，為語言學(xué)界培養(yǎng)了一批有素養(yǎng)的學(xué)者。養(yǎng)的學(xué)者。2021/3/9221.2.5 文法和語言的類型文法和語言的類型定義

18、定義1.11 設(shè)文法G = (V, T, P, S)，如果，對于P，滿足(VT)+且中至少含有一個非終結(jié)符，(VT)*，則G稱為0型文法（或短語結(jié)構(gòu)文法，簡記為PSG)或者無約束文法(Unrestricted Grammar)。0型文法能確保產(chǎn)生式的左部不為空。 由0型文法所生成的語言稱為0型語言或短語結(jié)構(gòu)語言（簡記為PSL）。0型文法的能力與圖靈機(jī)（Turing Machine）相當(dāng)。王雷版權(quán)所有2021/3/9231.2.5 文法和語言的類型文法和語言的類型定義定義1.12 設(shè)文法G = (V, T, P, S)，如果對于P，滿足|(除S外)，則文法G稱為1型文法或上下文有關(guān)文法，簡記為C

19、SG。1型文法的產(chǎn)生式的形式也被描述為：1A212，其中： 1、2 、(VT)+，AV。它更能體現(xiàn)“上下文有關(guān)”這一含義，因為，只有A出現(xiàn)在1和2之間（1為A的上文， 2為A的下文），才允許用來取代A。1型文法所產(chǎn)生的語言稱作1型語言或上下文有關(guān)語言(簡記為CSL)。王雷版權(quán)所有2021/3/9241.2.5 文法和語言的類型文法和語言的類型定義定義1.13 設(shè)文法G = (V, T, P, S)，如果，對于P，滿足V，(VT)*，則稱G為2型文法或上下文無關(guān)文法，簡記為CFG。上下文無關(guān)文法取名為“上下文無關(guān)”的原因就是因為字符 總可以被字串 自由替換，而無需考慮字符 出現(xiàn)的上下文。2型文法

20、所產(chǎn)生的語言稱作2型語言或上下文無關(guān)語言(簡記為CFL)。一個簡單的上下文無關(guān)文法的例子是：S - aSb | 。由于這個文法的產(chǎn)生式的左邊都是單個的非終結(jié)符S，右邊是由終結(jié)符或非終結(jié)符構(gòu)成的符號串a(chǎn)Sb和，因此符合上下文無關(guān)語法產(chǎn)生式的要求。該文法產(chǎn)生的語言為 anbn : n 0 。王雷版權(quán)所有2021/3/9251.2.5 文法和語言的類型文法和語言的類型定義定義1.14：設(shè)文法G = (V, T, P, S)，如果P中的每一條產(chǎn)生式都是AaB或Aa形式，其中：A、BV ，aT ，則稱G為3型文法或正規(guī)文法, 簡記為RG。3型文法所產(chǎn)生的語言稱作3型語言或正規(guī)語言(簡記為RL)。3型語言

21、與有限自動機(jī)等價，即有限自動機(jī)恰能識別3型語言。 0型語言1型語言2型語言3型語言圖1.4 形式語言的Chomsky層級在忽略句子的情況下，由Chomsky分類定義可知，任何3型語言都是2型語言，任何2型語言都是1型語言，任何1型語言都是0型語言。王雷版權(quán)所有2021/3/9261.2.5 文法和語言的類型文法和語言的類型王雷版權(quán)所有0型語言1型語言2型語言3型語言圖圖1.4 形式語言的形式語言的Chomsky層級層級2021/3/9271.3 正規(guī)表達(dá)式（正規(guī)式正規(guī)表達(dá)式（正規(guī)式 ）正規(guī)式是按照一組定義規(guī)則，由較簡單的正規(guī)式構(gòu)成的，每個正規(guī)式e表示一個語言L(e)（正規(guī)集合）。 定義定義1.

22、15 字母表上的正規(guī)表達(dá)式和正規(guī)集遞歸定義如下： 1、任意a，a是上的一個正規(guī)表達(dá)式，它所表示的正規(guī)集為a。 2、空串是上的一個正規(guī)表達(dá)式，它所表示的正規(guī)集為。 3、符號是上的一個正規(guī)表達(dá)式，它所表示的正規(guī)集為。 4、設(shè)e1與e2都是上的正規(guī)表達(dá)式，它們所表示的正規(guī)集分別為L(e1)與L(e2)，則 （1）e1 + e2也是正規(guī)表達(dá)式，它所表示的正規(guī)集為 L(e1 + e2) = L(e1)L(e2) （2）e1e2也是正規(guī)表達(dá)式，它所表示的正規(guī)集為 L(e1e2) = L(e1)L(e2) （3）(e1)*也是正規(guī)表達(dá)式，它所表示的正規(guī)集為 L(e1)*) = (L(e1)* 王雷版權(quán)所有2

23、021/3/9281.3 正規(guī)表達(dá)式（正規(guī)式正規(guī)表達(dá)式（正規(guī)式 ）例例1.7 令 = a, b，下面表列出了上的一些正規(guī)表達(dá)和相應(yīng)的正規(guī)集：王雷版權(quán)所有2021/3/9291.3 正規(guī)表達(dá)式（正規(guī)式正規(guī)表達(dá)式（正規(guī)式 ）正規(guī)式的代數(shù)性質(zhì)王雷版權(quán)所有2021/3/9301.3 正規(guī)表達(dá)式（正規(guī)式正規(guī)表達(dá)式（正規(guī)式 ）正規(guī)式和正規(guī)集之間并不存在一一對應(yīng)的關(guān)系。不同的正規(guī)式可能描述的是相同的正規(guī)集；例如： b(ab)*及(ba)*b都是b開頭且其后跟以零個或任意多個ab所組成的字符串兩個正規(guī)式等價，當(dāng)且僅當(dāng)它們描述的正規(guī)集相同。 = a, b上的a, b*上的任意一個子集不一定是正規(guī)集。例如，子集a

24、nbn | n 1就不是一個正規(guī)集，它不能用正規(guī)式來描述，也不能用正規(guī)文法（3型文法）來描述。因為正規(guī)文法和正規(guī)式均沒有這樣的能力來判斷或保證a的個數(shù)等于b的個數(shù)。但它可用上下文無關(guān)文法（2型文法） S - aSb | ab來描述。王雷版權(quán)所有2021/3/9311.3 正規(guī)表達(dá)式（正規(guī)式正規(guī)表達(dá)式（正規(guī)式 ）正規(guī)表達(dá)式運算符的優(yōu)先級順序正規(guī)表達(dá)式運算符的優(yōu)先級順序最高優(yōu)先級的是閉包運算（星閉包*和正閉包+），它類似于代數(shù)運算中的冪運算。其次優(yōu)先級的是“聯(lián)結(jié)”運算符，它類似于代數(shù)運算中的乘法。優(yōu)先級別最低的是“并”運算（+運算符）。它類似于代數(shù)運算中的加法。 通過在正規(guī)表達(dá)式中添加括號可以改變

25、運算的優(yōu)先級。王雷版權(quán)所有2021/3/9321.4 正規(guī)文法與正規(guī)式正規(guī)文法與正規(guī)式一個正規(guī)語言可以由正規(guī)文法定義，也可由正規(guī)式定義，對任意一個正規(guī)文法，存在一個定義同一個語言的正規(guī)式；反之，對于每一個正規(guī)式，存在一個生成同一語言的正規(guī)文法。正規(guī)表達(dá)式和正規(guī)文法正規(guī)表達(dá)式和正規(guī)文法 之間是可以互相轉(zhuǎn)換的。王雷版權(quán)所有2021/3/9331.4 正規(guī)文法與正規(guī)式正規(guī)文法與正規(guī)式正規(guī)表達(dá)式轉(zhuǎn)換成正規(guī)文法正規(guī)表達(dá)式轉(zhuǎn)換成正規(guī)文法 將上的一個正規(guī)表達(dá)式r轉(zhuǎn)換成正規(guī)文法G = （V，T，S，P）的方法如下： 1、令T = ； 2、選擇一個非終結(jié)符S，生成規(guī)則S r，并將S定為G的開始符號。 3、若x和y都是正規(guī)式，則： (1) 對形如A xy的規(guī)則，重寫成A xB,，B y兩個規(guī)則，其中B是新選擇的非終結(jié)符，即BV。 (2) 對形如A(x + y)B的規(guī)則，重寫成A xB，A yB兩個規(guī)則。 (3) 對形如Ax + y的規(guī)則，重寫成A x，A y兩個規(guī)則。 (4) 對已轉(zhuǎn)換的文法中形如Ax*y的規(guī)則，重寫成A xA，A y兩個規(guī)則。4、不斷利用上述規(guī)則進(jìn)行變換，直到每一條規(guī)則最多有一個終結(jié)符為止。 王雷版權(quán)所有2021/3/9341.4 正規(guī)文法與正規(guī)式正規(guī)文