《計(jì)算機(jī)數(shù)學(xué)基礎(chǔ)課件》由會(huì)員分享，可在線閱讀，更多相關(guān)《計(jì)算機(jī)數(shù)學(xué)基礎(chǔ)課件(37頁珍藏版)》請(qǐng)?jiān)谌巳宋膸炀W(wǎng)上搜索。

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

2、算,符號(hào)串的聯(lián)結(jié)：聯(lián)結(jié)是符號(hào)串的基本運(yùn)算。兩個(gè)符號(hào)串X和Y的聯(lián)結(jié)，記為XY，就是把Y跟隨在X的后面形成的符號(hào)串。,例1.1：設(shè) = 1, 2是一個(gè)字母表。設(shè)X = 11、Y = 22分別是上的兩個(gè)符號(hào)串。則： XY = 1122是X、Y兩個(gè)符號(hào)串的聯(lián)結(jié)，XY是上的一符號(hào)串。 YX = 2211是Y、X兩個(gè)符號(hào)串的聯(lián)結(jié)，YX也是上的一符號(hào)串。,一般來說，符號(hào)串的聯(lián)結(jié)不滿足交換律。顯然符號(hào)串的聯(lián)結(jié)是滿足結(jié)合律的，即有，(XY)Z = X(YZ)。在例1.1中，顯然有XYYX，(XY)X = X(YX) = 112211。,王雷版權(quán)所有,1.1 符號(hào)、符號(hào)串及其運(yùn)算,由于是不含符號(hào)的符號(hào)串(空串)，。

3、所以對(duì)任意符號(hào)串X都有，X = X = X。由此我們可以認(rèn)為是符號(hào)串聯(lián)結(jié)運(yùn)算的單位元。,符號(hào)串的方冪：設(shè)X是符號(hào)串，把X自身聯(lián)結(jié)n次后，得到的符號(hào)串Z，即Z = XXXX = Xn，稱為X的方冪。我們約定X0 = 。這個(gè)定義可以遞歸地表示為：,A,B,王雷版權(quán)所有,1.1 符號(hào)、符號(hào)串及其運(yùn)算,符號(hào)串的子串、前綴和后綴： 符號(hào)串V是符號(hào)串W的子串，當(dāng)且僅當(dāng)存在符號(hào)串X和Y，使得W = XVY。這里，X和Y都可能是空串。,集合的聯(lián)結(jié)：設(shè)A和B都是符號(hào)串的集合，定以集合A和B的聯(lián)結(jié)為： AB = XY | XA且YB， 即集合A和B的聯(lián)結(jié)是集合A中的符號(hào)串和集合B中的符號(hào)串的聯(lián)結(jié)所構(gòu)成的集合。,A。

4、,B,王雷版權(quán)所有,1.1 符號(hào)、符號(hào)串及其運(yùn)算,集合的方冪：設(shè)A是符號(hào)串的集合，把A自身聯(lián)結(jié)n次后，得到的新的集合An，即An = AAA，稱為集合A的方冪。 我們約定A0 = 。這個(gè)定義可以遞歸地表示為：,王雷版權(quán)所有,1.1 符號(hào)、符號(hào)串及其運(yùn)算,集合的閉包和正閉包：設(shè)A是符號(hào)串的集合，用A*表示A的所有的有限次方冪的并集，則稱A*為集合A上的閉包，即：,注意：閉包A*與正閉包A+的差別在于是否包含空串。在閉包A*中去掉空串后就成為正閉包A+。A* 具有可數(shù)無窮多的符號(hào)串。,A* = A0A1A2An 而稱A+ = A1A2An 為A上的正閉包，顯然,有 A* = A0 A+ ， A+ 。

5、= A*A = AA*。,語言：令為一個(gè)字母表。若L *，則L是字母表上的一個(gè)語言。 即：L為一個(gè)由字母表上的字符串所構(gòu)成的集合。,王雷版權(quán)所有,1.2 文法與語言的形式定義,語言都是用文法來描述的。 一個(gè)文法實(shí)際上是一組有限的規(guī)則式。,非終結(jié)符(一種過渡性符號(hào))：也是一種符號(hào)，但不是字母表中的符號(hào)。我們將它記為V。,終結(jié)符：是一個(gè)語言的字母表中的符號(hào)。我們將它記為T。,對(duì)于一個(gè)形式語言L，設(shè)T和V分別是它的終結(jié)符集和非終結(jié)符集，顯然有L T*，且TV = 。,王雷版權(quán)所有,1. 2. 1 文法的形式化定義,王雷版權(quán)所有,1. 2. 1 文法的形式化定義,王雷版權(quán)所有,1. 2. 1 文法的形。

6、式化定義,王雷版權(quán)所有,1. 2. 2 推導(dǎo)的形式化定義,王雷版權(quán)所有,1. 2. 2 推導(dǎo)的形式化定義,王雷版權(quán)所有,1. 2. 2 推導(dǎo)的形式化定義,規(guī)范句型、短語、直接短語和句柄,定義1. 5：給定一個(gè)文法G = (V, T, P, S)，如果符號(hào)串x是從文法G的開始符號(hào)S推導(dǎo)出來的，即S *x，則稱x是文法G的句型。如果符號(hào)串x是僅由終結(jié)符組成的句型，即S*x且xT*，則稱x是文法G的句子。 由規(guī)范推導(dǎo)所得到的句型就稱之為規(guī)范句型。,王雷版權(quán)所有,1. 2. 2 推導(dǎo)的形式化定義,規(guī)范句型、短語、直接短語和句柄,定義1. 6 設(shè)GS是一文法，x = w是一句型， 如果：S*A且A * 。

7、w 則稱w是句型x的一個(gè)相對(duì)于非終結(jié)符A的短語； 如果：S*A且Aw 則稱w是句型x的一個(gè)相對(duì)于非終結(jié)符的直接短語(或簡單短語)； 如果w是一個(gè)句型x的最左直接短語，稱w為句型x的句柄。,王雷版權(quán)所有,1.2.3 語言的形式化定義,王雷版權(quán)所有,1.2.3 語言的形式化定義,王雷版權(quán)所有,1.2.3 語言的形式化定義,王雷版權(quán)所有,1.2.4 語法樹,王雷版權(quán)所有,1.2.4 語法樹,定義1.9 如果一個(gè)文法存在某個(gè)句子對(duì)應(yīng)兩棵以上的不同的語法樹，或有兩個(gè)以上的不同的最左(右)推導(dǎo)，則稱該文法是二義性文法(程序設(shè)計(jì)語言不能有二義性 )。,定義1.10 如果一個(gè)語言L的任何文法都是二義性文法，則。

8、稱該語言L是二義性語言。 在理論上已經(jīng)證明了，存在著這種二義性的語言。 文法的二義性與語言的二義性是兩個(gè)不同的概念。,A,B,王雷版權(quán)所有,1.2.5 文法和語言的類型,王雷版權(quán)所有,諾姆喬姆斯基(Noam Chomsky, 1928-)，美國語言學(xué)家，轉(zhuǎn)換-生成語法的創(chuàng)始人。1928年12月7日出生于美國賓夕法尼亞州的費(fèi)城。1947年，在哈里斯的影響下他開始研究語言學(xué)。1951年在賓夕法尼亞大學(xué)完成碩士論文現(xiàn)代希伯萊語語素音位學(xué)，1955年在該校完成博士論文轉(zhuǎn)換分析，獲得博士學(xué)位。從1955年秋天開始，他一直在麻省理工學(xué)院工作，曾任該校語言學(xué)與哲學(xué)系主任，并任該校認(rèn)知科學(xué)研究中心主任，為語言。

9、學(xué)界培養(yǎng)了一批有素養(yǎng)的學(xué)者。,1.2.5 文法和語言的類型,王雷版權(quán)所有,1.2.5 文法和語言的類型,王雷版權(quán)所有,1.2.5 文法和語言的類型,王雷版權(quán)所有,1.2.5 文法和語言的類型,王雷版權(quán)所有,1.2.5 文法和語言的類型,王雷版權(quán)所有,1.3 正規(guī)表達(dá)式(正規(guī)式 ),王雷版權(quán)所有,1.3 正規(guī)表達(dá)式(正規(guī)式 ),王雷版權(quán)所有,1.3 正規(guī)表達(dá)式(正規(guī)式 ),王雷版權(quán)所有,1.3 正規(guī)表達(dá)式(正規(guī)式 ),王雷版權(quán)所有,1.3 正規(guī)表達(dá)式(正規(guī)式 ),正規(guī)表達(dá)式運(yùn)算符的優(yōu)先級(jí)順序,王雷版權(quán)所有,1.4 正規(guī)文法與正規(guī)式,一個(gè)正規(guī)語言可以由正規(guī)文法定義，也可由正規(guī)式定義，對(duì)任意一個(gè)正規(guī)文法，存在一個(gè)定義同一個(gè)語言的正規(guī)式；反之，對(duì)于每一個(gè)正規(guī)式，存在一個(gè)生成同一語言的正規(guī)文法。,正規(guī)表達(dá)式和正規(guī)文法 之間是可以互相轉(zhuǎn)換的。,王雷版權(quán)所有,1.4 正規(guī)文法與正規(guī)式,正規(guī)表達(dá)式轉(zhuǎn)換成正規(guī)文法,王雷版權(quán)所有,1.4 正規(guī)文法與正規(guī)式,將正規(guī)文法轉(zhuǎn)換成正規(guī)式,王雷版權(quán)所有,1.4 正規(guī)文法與正規(guī)式,將正規(guī)文法轉(zhuǎn)換成正規(guī)式,王雷版權(quán)所有,1.4 正規(guī)文法與正規(guī)式,將正規(guī)文法轉(zhuǎn)換成正規(guī)式,王雷版權(quán)所有,Thank You !,王雷 湘潭大學(xué)信息工程學(xué)院 2012版權(quán)所有。

總結(jié)

以上是生活随笔為你收集整理的计算机数学基础 视频讲解,计算机数学基础课件的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。