形式語(yǔ)言與自動(dòng)機(jī)weekIntroduction(張雷注)

1、1College of Computer Science & Technology, BUPTFormal Languages and Automata 課程名稱課程名稱 形式語(yǔ)言與自動(dòng)機(jī)形式語(yǔ)言與自動(dòng)機(jī) 教師姓名教師姓名 張雷張雷 （計(jì)算機(jī)學(xué)院（計(jì)算機(jī)學(xué)院 通信軟件工程中心）通信軟件工程中心） 電話電話 6228 3791 Office 教三樓教三樓 616 信箱信箱 講義教案講義教案 2College of Computer Science & Technology, BUPT緒論緒論n 課程信息課程信息n 為什么學(xué)習(xí)形式語(yǔ)言與自動(dòng)機(jī)為什么學(xué)習(xí)形式語(yǔ)言與自動(dòng)機(jī)n 形式語(yǔ)言與

2、自動(dòng)機(jī)概述及應(yīng)用形式語(yǔ)言與自動(dòng)機(jī)概述及應(yīng)用n 課程內(nèi)容及要求課程內(nèi)容及要求3College of Computer Science & Technology, BUPT 專業(yè)基礎(chǔ)課專業(yè)基礎(chǔ)課 - 上世紀(jì)上世紀(jì) 60 60 年代末、年代末、7070年代初，年代初，研究的高峰研究的高峰- 之后，向應(yīng)用領(lǐng)域滲透，之后，向應(yīng)用領(lǐng)域滲透，研究生課程研究生課程- 近幾年，近幾年，本科階段的專業(yè)基礎(chǔ)課本科階段的專業(yè)基礎(chǔ)課 專業(yè)工作者必須的理論素養(yǎng)專業(yè)工作者必須的理論素養(yǎng) - 計(jì)算模型計(jì)算模型 計(jì)算機(jī)（不）能夠做什么計(jì)算機(jī)（不）能夠做什么 - 問(wèn)題分類問(wèn)題分類 計(jì)算的復(fù)雜性，算法分析計(jì)算的復(fù)雜性，算法

3、分析 - 形式系統(tǒng)形式系統(tǒng) 建模工具（狀態(tài)機(jī)建模工具（狀態(tài)機(jī) ）- 抽象描述抽象描述 形式文法、形式表達(dá)式形式文法、形式表達(dá)式 課課 程程 性性 質(zhì)質(zhì)4College of Computer Science & Technology, BUPT相 關(guān) 課 程先修課程先修課程 - 離散數(shù)學(xué)離散數(shù)學(xué)（數(shù)理邏輯，集合論）（數(shù)理邏輯，集合論）- 計(jì)算機(jī)導(dǎo)論與程序設(shè)計(jì)、數(shù)據(jù)結(jié)構(gòu)計(jì)算機(jī)導(dǎo)論與程序設(shè)計(jì)、數(shù)據(jù)結(jié)構(gòu) 后續(xù)課程后續(xù)課程 - 編譯原理編譯原理 其它相關(guān)課程其它相關(guān)課程 模式識(shí)別、算法分析模式識(shí)別、算法分析 5College of Computer Science & Technolo

4、gy, BUPTn教材教材：形式語(yǔ)言與自動(dòng)機(jī)形式語(yǔ)言與自動(dòng)機(jī) 王柏王柏 楊娟楊娟 編著編著 北京郵電大學(xué)出版社北京郵電大學(xué)出版社 2003.16College of Computer Science & Technology, BUPT 經(jīng) 典 參 考 書 書名書名 Introduction to Automata Theory, Languages, and Computation （Second Edition） 作者作者 John E. Hopcroft （Cornell） Rajeev Motwani （Stanford） Jefferey D. Ullman （Stanfor

5、d） 出版社出版社 Addison Wesley （2001） 清華大學(xué)出版社清華大學(xué)出版社 （影印版）（影印版） First Edition 中譯本中譯本自動(dòng)機(jī)理論、語(yǔ)言和自動(dòng)機(jī)理論、語(yǔ)言和計(jì)算導(dǎo)引計(jì)算導(dǎo)引 徐美瑞徐美瑞 等譯等譯 科學(xué)出版社，科學(xué)出版社，1990 John.E.Hopcroft,the Turing Awardwinner in 1986.7College of Computer Science & Technology, BUPT 其它參 考 書 自動(dòng)機(jī)理論及其應(yīng)用自動(dòng)機(jī)理論及其應(yīng)用 何成武何成武 科學(xué)出版社科學(xué)出版社19901990形式語(yǔ)言及其句法分析形式語(yǔ)言及

6、其句法分析 美美A.V. A.V. 阿霍阿霍 等等 科學(xué)出版社科學(xué)出版社1987 1987 形式語(yǔ)言形式語(yǔ)言 王兵山，吳兵王兵山，吳兵 編編 國(guó)防工業(yè)大學(xué)出版社，國(guó)防工業(yè)大學(xué)出版社，19881988 形式語(yǔ)言與自動(dòng)機(jī)形式語(yǔ)言與自動(dòng)機(jī) 陳有祺陳有祺 編著編著 南開大學(xué)出版社，天津，南開大學(xué)出版社，天津，19991999 8College of Computer Science & Technology, BUPT2、為什么學(xué)習(xí)形式語(yǔ)言與自動(dòng)機(jī)為什么學(xué)習(xí)形式語(yǔ)言與自動(dòng)機(jī)n形式語(yǔ)言與自動(dòng)機(jī)是計(jì)算機(jī)科學(xué)的基礎(chǔ)理論形式語(yǔ)言與自動(dòng)機(jī)是計(jì)算機(jī)科學(xué)的基礎(chǔ)理論之一，是計(jì)算機(jī)學(xué)科的專業(yè)基礎(chǔ)課。之一，是計(jì)算

7、機(jī)學(xué)科的專業(yè)基礎(chǔ)課。n在人工智能、電信領(lǐng)域等有廣泛的應(yīng)用。在人工智能、電信領(lǐng)域等有廣泛的應(yīng)用。n通過(guò)一些定理的證明和應(yīng)用，對(duì)大家進(jìn)行思通過(guò)一些定理的證明和應(yīng)用，對(duì)大家進(jìn)行思維訓(xùn)練，從而為今后學(xué)習(xí)通信軟件，協(xié)議工維訓(xùn)練，從而為今后學(xué)習(xí)通信軟件，協(xié)議工程，編譯技術(shù)，人工智能等內(nèi)容提供理論基程，編譯技術(shù)，人工智能等內(nèi)容提供理論基礎(chǔ)。礎(chǔ)。9College of Computer Science & Technology, BUPT2、為什么學(xué)習(xí)形式語(yǔ)言與自動(dòng)機(jī)為什么學(xué)習(xí)形式語(yǔ)言與自動(dòng)機(jī)n對(duì)客觀世界的科學(xué)研究：目的在于把抽象數(shù)對(duì)客觀世界的科學(xué)研究：目的在于把抽象數(shù)學(xué)的形式化體系發(fā)展成為與現(xiàn)實(shí)生活

8、相似的學(xué)的形式化體系發(fā)展成為與現(xiàn)實(shí)生活相似的理論模型，從而提供一種通用結(jié)構(gòu)來(lái)描述、理論模型，從而提供一種通用結(jié)構(gòu)來(lái)描述、理解和解決問(wèn)題。理解和解決問(wèn)題。n計(jì)算機(jī)科學(xué)：是關(guān)于計(jì)算知識(shí)的有系統(tǒng)的整計(jì)算機(jī)科學(xué)：是關(guān)于計(jì)算知識(shí)的有系統(tǒng)的整體。體。10College of Computer Science & Technology, BUPT2、為什么學(xué)習(xí)形式語(yǔ)言與自動(dòng)機(jī)為什么學(xué)習(xí)形式語(yǔ)言與自動(dòng)機(jī)n計(jì)算機(jī)科學(xué)的兩個(gè)主要部分：n構(gòu)成計(jì)算基礎(chǔ)的一些基本概念和模型；n設(shè)計(jì)計(jì)算系統(tǒng)(軟件和硬件)的工程技術(shù)（設(shè)計(jì)理論的應(yīng)用）n本課程著重介紹第一部分（涉及到一些第二部分的應(yīng)用），通過(guò)形式化技術(shù)對(duì)大家進(jìn)行思維

9、訓(xùn)練，為今后的學(xué)習(xí)打好理論基礎(chǔ)。11College of Computer Science & Technology, BUPT3 3、形式語(yǔ)言與自動(dòng)機(jī)概述及應(yīng)用、形式語(yǔ)言與自動(dòng)機(jī)概述及應(yīng)用n本門課程將圍繞著什么是形式語(yǔ)言、什么是自動(dòng)機(jī)、以及形式語(yǔ)言和自動(dòng)機(jī)的相互關(guān)系進(jìn)行闡述。n核心內(nèi)容 - 有限狀態(tài)自動(dòng)機(jī)，正規(guī)語(yǔ)言，正規(guī)表達(dá)式- 上下文無(wú)關(guān)文法，上下文無(wú)關(guān)語(yǔ)言，下推 自動(dòng)機(jī)- 圖靈機(jī)，計(jì)算問(wèn)題分類12College of Computer Science & Technology, BUPT3.1 形式語(yǔ)言n什么是形式語(yǔ)言什么是形式語(yǔ)言n形式語(yǔ)言: 形式化描述的字母表上的字符

10、串的集形式化描述的字母表上的字符串的集合。合。n字母表：字符的有限集合。ne.g.：26個(gè)英文字母構(gòu)成的字母表。n字符串：字母表中的字符構(gòu)成的有限序列。ne.g. hello, afjhkfyu 13College of Computer Science & Technology, BUPT為什么用形式語(yǔ)言為什么用形式語(yǔ)言n自然語(yǔ)言自然語(yǔ)言：人們平時(shí)說(shuō)話時(shí)所使用的一種語(yǔ)：人們平時(shí)說(shuō)話時(shí)所使用的一種語(yǔ)言，不同的國(guó)家和民族有著不同的語(yǔ)言。言，不同的國(guó)家和民族有著不同的語(yǔ)言。n形式語(yǔ)言形式語(yǔ)言n通過(guò)人們公認(rèn)的符號(hào)，表達(dá)方式所描述的通過(guò)人們公認(rèn)的符號(hào)，表達(dá)方式所描述的一種語(yǔ)言，是一種通用語(yǔ)言，

11、沒有國(guó)籍之一種語(yǔ)言，是一種通用語(yǔ)言，沒有國(guó)籍之分。分。n形式語(yǔ)言是某個(gè)字母表上的字符串的集合，形式語(yǔ)言是某個(gè)字母表上的字符串的集合，有一定的描述范圍。有一定的描述范圍。14College of Computer Science & Technology, BUPT為什么用形式語(yǔ)言為什么用形式語(yǔ)言n例例1： 漢語(yǔ)：漢語(yǔ)： 用數(shù)用數(shù)字、符號(hào)等形式化的東西來(lái)描述語(yǔ)言字、符號(hào)等形式化的東西來(lái)描述語(yǔ)言n我吃飯我吃飯 語(yǔ)法正確語(yǔ)法正確n我飯吃我飯吃 語(yǔ)法錯(cuò)誤語(yǔ)法錯(cuò)誤n飯吃我飯吃我 語(yǔ)法正確，語(yǔ)義錯(cuò)誤語(yǔ)法正確，語(yǔ)義錯(cuò)誤15College of Computer Science & Techn

12、ology, BUPT為什么用形式語(yǔ)言為什么用形式語(yǔ)言n例2：T為PASCAL語(yǔ)言所用的全部符號(hào)的集合。n正確的PASCAL程序就是T上的語(yǔ)言。n例3：在字母表T=a上，L = a 2n+1 | n =0 n表示任意一對(duì)aa (包括0對(duì)) 后跟一個(gè)a的字符串。（即含有奇數(shù)個(gè)a的字符串。）16College of Computer Science & Technology, BUPT為什么用形式語(yǔ)言為什么用形式語(yǔ)言n形式語(yǔ)言的最初起因： 語(yǔ)言學(xué)家（Chomsky）想用一套形式化方法來(lái)描述語(yǔ)言。n形式語(yǔ)言在自然語(yǔ)言研究中起步，在計(jì)算機(jī)科學(xué)中得到廣泛應(yīng)用。n最初的應(yīng)用：編譯 讓計(jì)算機(jī)按照語(yǔ)法

13、規(guī)則將高級(jí)語(yǔ)言方便地翻譯成機(jī)器語(yǔ)言。17College of Computer Science & Technology, BUPT為什么用形式語(yǔ)言為什么用形式語(yǔ)言n現(xiàn)在： 已廣泛應(yīng)用在人工智能、圖象處理、通信協(xié)議、通信軟件等多個(gè)領(lǐng)域n在計(jì)算機(jī)理論科學(xué)方面： 是可計(jì)算理論（算法在有限步驟內(nèi)求得解、算法復(fù)雜性、停機(jī)問(wèn)題、）、定理自動(dòng)證明、程序轉(zhuǎn)換（程序自動(dòng)生成）、模式識(shí)別等的基礎(chǔ)。18College of Computer Science & Technology, BUPT為什么用形式語(yǔ)言為什么用形式語(yǔ)言n比爾.蓋茨：人類計(jì)算的未來(lái)是讓計(jì)算機(jī)能夠看、聽、學(xué)，能用自然語(yǔ)言與人類交

14、流 n形式化非常重要19College of Computer Science & Technology, BUPT 3.2. 3.2. 自動(dòng)機(jī)自動(dòng)機(jī)n什么是自動(dòng)機(jī)？具有離散輸入輸出的數(shù)學(xué)模型。包括：n輸入裝置讀頭+輸入帶n控制部件。 狀態(tài)轉(zhuǎn)移n存儲(chǔ)單元n大量通信軟件的基本工作機(jī)制都是有限狀態(tài)自動(dòng)機(jī)。自動(dòng)機(jī)理論在通信領(lǐng)域中的應(yīng)用極為廣泛。20College of Computer Science & Technology, BUPT 3.2. 3.2. 自動(dòng)機(jī)自動(dòng)機(jī)n自動(dòng)機(jī)接受一定的輸入，執(zhí)行一定的動(dòng)作，產(chǎn)生一定的結(jié)果。使用狀態(tài)遷移描述整個(gè)工作過(guò)程。n狀態(tài)狀態(tài)：一個(gè)標(biāo)識(shí)，能區(qū)分

15、自動(dòng)機(jī)在不同時(shí)刻的狀況。有限狀態(tài)系統(tǒng)具有任意有限數(shù)目的內(nèi)部“狀態(tài)”n自動(dòng)機(jī)的本質(zhì)自動(dòng)機(jī)的本質(zhì)：根據(jù)狀態(tài)、輸入和規(guī)則決定下一個(gè)狀態(tài)狀態(tài)狀態(tài) 輸入（激勵(lì)）輸入（激勵(lì)） 規(guī)則規(guī)則 狀態(tài)遷移狀態(tài)遷移21College of Computer Science & Technology, BUPT為什么叫自動(dòng)機(jī)？為什么叫自動(dòng)機(jī)？n可能的狀態(tài)、運(yùn)行的規(guī)則都是事先確定的。一旦開始運(yùn)行，就按照事先確定的規(guī)則工作，因此叫“自動(dòng)機(jī)”。n有限自動(dòng)機(jī)可以認(rèn)為是由一個(gè)帶有讀頭的有限控制器和一條寫有字符的輸入帶組成。22College of Computer Science & Technology, BU

16、PT自動(dòng)機(jī)舉例n例1：打電話 (自動(dòng)機(jī)在通信領(lǐng)域的應(yīng)用)。 在一次呼叫中，從建立連接到通話完畢，要經(jīng)歷摘機(jī)，撥號(hào)，應(yīng)答，進(jìn)行通話等過(guò)程，可以分別用四個(gè)狀態(tài)來(lái)表示。q0q0q1q1q2q2q3q3q4q4摘機(jī)摘機(jī)收到撥號(hào)音收到撥號(hào)音撥號(hào)撥號(hào)收應(yīng)答信號(hào)收應(yīng)答信號(hào)掛機(jī)掛機(jī)收齊號(hào)碼收齊號(hào)碼q0:q0:空閑狀態(tài)空閑狀態(tài)q1:q1:等待撥號(hào)狀態(tài)等待撥號(hào)狀態(tài)q2:q2:可以撥號(hào)狀態(tài)可以撥號(hào)狀態(tài)q3:q3:等待應(yīng)答狀態(tài)等待應(yīng)答狀態(tài)q4:q4:通話狀態(tài)通話狀態(tài)23College of Computer Science & Technology, BUPT自動(dòng)機(jī)舉例n例2：串口通信 兩臺(tái)微機(jī)通過(guò)串口通信,

17、 需在兩臺(tái)機(jī)器間建立好連接后，才可以傳遞數(shù)據(jù)，可以使用有限狀態(tài)自動(dòng)機(jī)，描述串口通信的狀態(tài)。傳輸數(shù)據(jù)收到應(yīng)答斷開連接連接請(qǐng)求q0q1q224College of Computer Science & Technology, BUPT自動(dòng)機(jī)舉例n例3。在許多數(shù)字電子技術(shù)基礎(chǔ)教科書中，串行序列檢測(cè)電路設(shè)計(jì)常常被作為同步時(shí)序電路設(shè)計(jì)的一個(gè)例題。要求設(shè)計(jì)“111”序列檢測(cè)電路。它要求電路有一個(gè)串行輸入端X 及一個(gè)串行輸出端Z，當(dāng)輸入序列連續(xù)輸入3個(gè)1時(shí)，輸出為1，否則輸出為0。 25College of Computer Science & Technology, BUPT26Colle

18、ge of Computer Science & Technology, BUPT自動(dòng)機(jī)的分類n根據(jù)結(jié)構(gòu)不同，自動(dòng)機(jī)又可分為有限自動(dòng)機(jī)，下推自動(dòng)機(jī)，圖靈機(jī)等。n下推自動(dòng)機(jī)可以看作是由一條輸入帶，一個(gè)有限控制器和一個(gè)下推棧組成。n基本圖靈機(jī)由一個(gè)具有讀寫頭的有限控制器和一條無(wú)限帶組成。n使用自動(dòng)機(jī)，可以形式化的描述現(xiàn)實(shí)世界中的一些問(wèn)題。27College of Computer Science & Technology, BUPT3 3.3 .3 形式語(yǔ)言與自動(dòng)機(jī)的關(guān)系形式語(yǔ)言與自動(dòng)機(jī)的關(guān)系n形式語(yǔ)言和自動(dòng)機(jī)是密切相關(guān)的。形式語(yǔ)言 字符串自動(dòng)機(jī) 字符串的識(shí)別系統(tǒng)n根據(jù)復(fù)雜程度可將

19、形式語(yǔ)言分類，根據(jù)自動(dòng)機(jī)的接受能力、處理能力的不同也將自動(dòng)機(jī)分類。二者之間具有較好的對(duì)應(yīng)關(guān)系。28College of Computer Science & Technology, BUPT3 3.3 .3 形式語(yǔ)言與自動(dòng)機(jī)的關(guān)系形式語(yǔ)言與自動(dòng)機(jī)的關(guān)系29College of Computer Science & Technology, BUPT語(yǔ)言與有限自動(dòng)機(jī)（Finite Automata） 設(shè)設(shè) = 0, 1 ， L = w w 中至少有一個(gè)中至少有一個(gè)0 ， 如如 0011, 10, 110111 L, 而而11, , 1111 L。下圖是一個(gè)可接受該語(yǔ)言的有限狀態(tài)自動(dòng)

20、機(jī)下圖是一個(gè)可接受該語(yǔ)言的有限狀態(tài)自動(dòng)機(jī) 12Start0, 10130College of Computer Science & Technology, BUPT小結(jié)n文法是定義語(yǔ)言的一個(gè)數(shù)學(xué)模型，而自動(dòng)機(jī)可看作是語(yǔ)言的識(shí)別系統(tǒng)。n通過(guò)對(duì)一些定理的證明，說(shuō)明對(duì)于一個(gè)文法產(chǎn)生的語(yǔ)言，可以構(gòu)造相應(yīng)自動(dòng)機(jī)接受該語(yǔ)言：一個(gè)自動(dòng)機(jī)接受的語(yǔ)言，可以構(gòu)造對(duì)應(yīng)的文法產(chǎn)生該語(yǔ)言。一定類型的自動(dòng)機(jī)和某種類型的文法具有等價(jià)性。 31College of Computer Science & Technology, BUPT課程內(nèi)容及要求n課程內(nèi)容： 書上二、三、四、五、六章。n要求：通過(guò)本課學(xué)習(xí)，

21、要求同學(xué)們掌握形式化描述方法，建立起形式語(yǔ)言與自動(dòng)機(jī)的概念，并能在實(shí)際中加以應(yīng)用。n通過(guò)對(duì)定理的證明，對(duì)同學(xué)們進(jìn)行思維訓(xùn)練，并掌握一定的證明方法。32College of Computer Science & Technology, BUPT證 明 技 術(shù)* 定義、定理和證明定義、定理和證明基本證明方法基本證明方法 歸納證明技術(shù)歸納證明技術(shù)* 引自清華大學(xué)計(jì)算機(jī)系軟件技術(shù)研究所王生原老師課件引自清華大學(xué)計(jì)算機(jī)系軟件技術(shù)研究所王生原老師課件33College of Computer Science & Technology, BUPT定義、定理和證明n定義：對(duì)象和概念的描述。定義

22、需要精確，明確說(shuō)定義：對(duì)象和概念的描述。定義需要精確，明確說(shuō)明對(duì)象的構(gòu)成。明對(duì)象的構(gòu)成。n命題：描述某個(gè)對(duì)象所具有的某種命題：描述某個(gè)對(duì)象所具有的某種性質(zhì)。性質(zhì)。也需精確。也需精確。n證明：邏輯論證，確認(rèn)一個(gè)命題為真。證明：邏輯論證，確認(rèn)一個(gè)命題為真。n定理：被證明為真的（數(shù)學(xué)）命題。定理：被證明為真的（數(shù)學(xué)）命題。n引理：被證明的命題，有助于證明另一個(gè)更有意義引理：被證明的命題，有助于證明另一個(gè)更有意義的命題的命題34College of Computer Science & Technology, BUPT演 繹 證 明 概念概念 一個(gè)一個(gè) 證明證明（proof）是命題的序列，是命

23、題的序列，其中的每一個(gè)命題或者是已知的命題，或者是其中的每一個(gè)命題或者是已知的命題，或者是由前面出現(xiàn)過(guò)的命題使用邏輯公理和規(guī)則得出由前面出現(xiàn)過(guò)的命題使用邏輯公理和規(guī)則得出. 已知的命題集合稱為已知的命題集合稱為假設(shè)假設(shè)（hypothesis）或或前前提提（premise），），最后一個(gè)命最后一個(gè)命 題稱為該前提的題稱為該前提的結(jié)論結(jié)論（conclusion）. 35College of Computer Science & Technology, BUPT“If If Then Then”命題命題 證明方法證明方法 把把 If 部分作為已知的命題，把部分作為已知的命題，把 Then 部

24、分作部分作為結(jié)論為結(jié)論. 舉例舉例 如果如果x+y=1，那么那么x2-y2=x-y. 證明證明:1 x2-y2 = (x+y)(x-y) / 數(shù)學(xué)數(shù)學(xué)公理公理2 (x+y) = 1 / 已知已知x2-y2 = x-y / 由由1、2 和算術(shù)性質(zhì)推出和算術(shù)性質(zhì)推出 36College of Computer Science & Technology, BUPT“If - And - Only - If If - And - Only - If ”命題命題 欲證欲證 A if and only if B， 可分別證明如下兩個(gè)命題：可分別證明如下兩個(gè)命題： 1 if A then B， 2

25、if B then A. 37College of Computer Science & Technology, BUPT有關(guān)集合的命題有關(guān)集合的命題 在本課程中，經(jīng)常要證明兩種不同方法構(gòu)造的在本課程中，經(jīng)常要證明兩種不同方法構(gòu)造的集合是相同的集合（比如語(yǔ)言表達(dá)的等價(jià)性）。集合是相同的集合（比如語(yǔ)言表達(dá)的等價(jià)性）。設(shè)設(shè) R, S 為集合的表達(dá)式，下面兩個(gè)命題的證明為集合的表達(dá)式，下面兩個(gè)命題的證明需要參照集合的定義，分別表示為如下的命題。需要參照集合的定義，分別表示為如下的命題。 欲證欲證 R S， 可證明如下命題：可證明如下命題： if x R then x S 欲證欲證 R = S

26、， 可分別證明如下兩個(gè)命題：可分別證明如下兩個(gè)命題： 1 if x R then x S 2 if x S then x R38College of Computer Science & Technology, BUPT原命題的逆否命題原命題的逆否命題有時(shí)，證明原命題的逆否有時(shí)，證明原命題的逆否(contrapositive) 命題更加方便命題更加方便. 欲證欲證 if A then B ， 可證明如下命題：可證明如下命題： if not B then not A原因：兩個(gè)命題是等價(jià)，原因：兩個(gè)命題是等價(jià)， （蘊(yùn)涵邏輯等價(jià)）。（蘊(yùn)涵邏輯等價(jià)）。39College of Computer

27、 Science & Technology, BUPT反證法反證法 反證（反證（proof by contradiction） 欲證欲證 if H then C ，可以把可以把 H 和和 not C 都作為已知的命題，把任何一個(gè)矛盾都作為已知的命題，把任何一個(gè)矛盾( contradiction )命題作為新的結(jié)論命題作為新的結(jié)論.40College of Computer Science & Technology, BUPT舉例證明或否證舉例證明或否證 舉例證明存在量化的命題舉例證明存在量化的命題 如命題：存在整數(shù)如命題：存在整數(shù) a，滿足滿足 a2 = 2a. 證明證明: 取

28、取 a = 2. ，滿足滿足 a2 = 2a. 舉反例否定全稱量化的命題舉反例否定全稱量化的命題 如命題：所有整數(shù)如命題：所有整數(shù) a，都滿足都滿足 a2=2a. 否證否證: 取取 a = 1. ，不滿足不滿足 a2 = 2a. 41College of Computer Science & Technology, BUPT 歸納證明在處理遞歸定義的對(duì)象時(shí)歸納證明在處理遞歸定義的對(duì)象時(shí)“必不可少必不可少”。在自動(dòng)機(jī)理論中，需要?dú)w納證明處理遞歸定義的概在自動(dòng)機(jī)理論中，需要?dú)w納證明處理遞歸定義的概念，比如：樹、表達(dá)式等。念，比如：樹、表達(dá)式等。歸納法原理：歸納法原理：如果證明了如果證明了S

29、(i),并且證明了對(duì)所有并且證明了對(duì)所有ni，S(n)蘊(yùn)涵蘊(yùn)涵S(n+1)，就可得出：對(duì)所有，就可得出：對(duì)所有ni, S(n)成立。成立。歸納證明與遞歸定義的對(duì)應(yīng)。歸納證明與遞歸定義的對(duì)應(yīng)。歸 納 證 明 與 結(jié) 構(gòu) 歸 納 法42College of Computer Science & Technology, BUPT歸 納 證 明 與 結(jié) 構(gòu) 歸 納 法集合的遞歸定義集合的遞歸定義 由由 3 部分構(gòu)成：部分構(gòu)成： 1 基礎(chǔ)基礎(chǔ)（basis） / 直接定義集合中的元素（至少直接定義集合中的元素（至少1個(gè)）個(gè)） 2 歸納歸納（induction）/ 從已知元素生成新元素的規(guī)則從已知元

30、素生成新元素的規(guī)則 3 極小性限制極小性限制 / 申明集合中的元素只能由申明集合中的元素只能由 1、2 生成生成 43College of Computer Science & Technology, BUPT歸 納 證 明 與 結(jié) 構(gòu) 歸 納 法結(jié)構(gòu)歸納法結(jié)構(gòu)歸納法 對(duì)于歸納（遞歸）定義的集合對(duì)于歸納（遞歸）定義的集合 S，欲證對(duì)于任意欲證對(duì)于任意x S，滿足性質(zhì)滿足性質(zhì)P(x). 1 基礎(chǔ)基礎(chǔ)（basis） / 若有直接定義若有直接定義 a S，則證明則證明 P(a) 2 歸納歸納（induction） / 若歸納定義中有規(guī)則若歸納定義中有規(guī)則 if a1, a2, , an S

31、then f (a1, a2, , an ) S ，則證明則證明 if P( a1 ), P( a2 ), , P( an ) S then P( f (a1, a2, , an ) ) 44College of Computer Science & Technology, BUPT 歸納定義歸納定義合法括號(hào)串的集合合法括號(hào)串的集合 S 1 基礎(chǔ)基礎(chǔ) 空串空串 S 2 歸納歸納 若若 x S ，則則 (x) S ； 若若 x,y S ，則則 xy S . 3 極小性限制極小性限制 S 中的元素只能由中的元素只能由 1、2 生成生成 (或：或： S是滿足是滿足1、2的最小集合的最小集合)

32、 命題：合法括號(hào)串集合命題：合法括號(hào)串集合 S 中每個(gè)括號(hào)串的中每個(gè)括號(hào)串的“(”與與“)”數(shù)目數(shù)目相等相等 證明證明: 1 基礎(chǔ)基礎(chǔ) 空串空串 的的“(”與與“)”數(shù)目相等，都為數(shù)目相等，都為0； 2 歸納歸納 設(shè)設(shè) x,y 的的“(”與與“)”數(shù)目相等，前者為數(shù)目相等，前者為m ，后者后者為為n ； (x) 的的“(”與與“)”數(shù)目都為數(shù)目都為m+1； xy 的的“(”與與“)”數(shù)目都為數(shù)目都為m+n. 歸納定義與結(jié)構(gòu)歸納證明（例）歸納定義與結(jié)構(gòu)歸納證明（例）45College of Computer Science & Technology, BUPT 自然數(shù)自然數(shù) 自然數(shù)集合自

33、然數(shù)集合N是滿足如下條件的最小集合：是滿足如下條件的最小集合： (1) 0 N; (2) 若若 n N, 則則n的后繼的后繼n+1 N 數(shù)學(xué)歸納法數(shù)學(xué)歸納法 欲證對(duì)任意自然數(shù)欲證對(duì)任意自然數(shù)n ，P(n)成立，成立，(1) 先證先證 P(0) 成立; (2) 再證若 P(n)成立, 則P(n+1 )成立 另一種形式另一種形式 (1) 先證先證P(0) 成立成立; (2) 再證若對(duì)任意再證若對(duì)任意kn， P(k) 成立成立, 則則P(n)成立成立 對(duì)任何良序集合，都可以有這兩種形式對(duì)任何良序集合，都可以有這兩種形式基于自然數(shù)的歸納基于自然數(shù)的歸納 一般數(shù)學(xué)歸納法一般數(shù)學(xué)歸納法46College

34、of Computer Science & Technology, BUPT第二章第二章 語(yǔ)言及文法語(yǔ)言及文法n主要內(nèi)容主要內(nèi)容：n定義形式語(yǔ)言的術(shù)語(yǔ)定義形式語(yǔ)言的術(shù)語(yǔ)n給出文法的定義和文法的分類給出文法的定義和文法的分類n要求掌握：要求掌握：n語(yǔ)言和文法的形式定義語(yǔ)言和文法的形式定義nCHOMSKY文法體系的分類。文法體系的分類。47College of Computer Science & Technology, BUPT第一節(jié)第一節(jié) 語(yǔ)言的定義與運(yùn)算語(yǔ)言的定義與運(yùn)算一、一、語(yǔ)言的一些術(shù)語(yǔ)：語(yǔ)言的一些術(shù)語(yǔ)：n 字母表：字母表： 字符的有限集合，記為字符的有限集合，記為T。

35、n字符串：字符串： 由字母表由字母表T中的字符構(gòu)成的序中的字符構(gòu)成的序列稱字母表列稱字母表T上的字符串（句子）。上的字符串（句子）。n 常記為常記為u,v,w,x,y,z；n 常用常用a,b,c,d 標(biāo)識(shí)單個(gè)字符。標(biāo)識(shí)單個(gè)字符。48College of Computer Science & Technology, BUPT字字 母母 表表 （AlphabetAlphabet） 概念概念 形式符號(hào)的集合形式符號(hào)的集合 記號(hào)記號(hào) 常用常用 T、 表示表示 舉例舉例- 英文字母表英文字母表 a, b, , z, A, B , , Z - 英文標(biāo)點(diǎn)符號(hào)表英文標(biāo)點(diǎn)符號(hào)表 , ; : . ? !

36、“ ” ( ) - 漢字表漢字表 , 自自, , 動(dòng)動(dòng) , , 機(jī)機(jī), - 化學(xué)元素表化學(xué)元素表 H, He, Li, , - T = a, n, y, 任任,意意 49College of Computer Science & Technology, BUPT字字 符符 串串 （stringstring） 概念概念 字母表字母表 T 上的一個(gè)上的一個(gè)字符串字符串（簡(jiǎn)稱（簡(jiǎn)稱串串），或稱為），或稱為 字字（word），），為為 T 中字符構(gòu)成的一個(gè)有限序列。中字符構(gòu)成的一個(gè)有限序列。 空串空串（empty string）, 用用 表示，不包含任何表示，不包含任何 字符。字符。 舉例舉例

37、 設(shè)設(shè) T = a, b ，則則 , a, ba, bbaba 等都是串等都是串 字符串字符串 w 的的長(zhǎng)度長(zhǎng)度，記為，記為 w ，是包含在是包含在 w 中字符的中字符的個(gè)數(shù)個(gè)數(shù) 舉例舉例 = 0， bbaba = 5 ai 表示含有表示含有i個(gè)個(gè)a的字符串的字符串 50College of Computer Science & Technology, BUPT 連接（連接（concatenation） 設(shè)設(shè) x, y為串為串, 且且 x a1a2 am, y b1b2 bn, 則則 x 與與 y 的連接的連接 x y a1a2 am b1b2 bn 連接運(yùn)算的性質(zhì)連接運(yùn)算的性質(zhì) -

38、( x y ) z x（ y z ）- x x x - x y x + y 關(guān)關(guān) 于于 字字 符符 串串 的的 運(yùn)運(yùn) 算算51College of Computer Science & Technology, BUPT 其它其它 如如 取頭字符取頭字符，取尾部取尾部，子串匹配子串匹配 等等n 設(shè)設(shè)1, 2, 3是字母表是字母表T上的字符串，稱：上的字符串，稱：n1是字符串是字符串12的的前綴前綴，n2是字符串是字符串12的的后綴后綴，n2是字符串是字符串123的的子串子串。 n 空串是任何字符串的前綴，后綴及子串?？沾侨魏巫址那熬Y，后綴及子串。n 例例：abc的前綴的前綴 a a

39、b abc . 后綴后綴 c bc abc . 子串子串 a b c ab bc abc , 即一個(gè)字符串可以看作是多個(gè)字符串的連接。即一個(gè)字符串可以看作是多個(gè)字符串的連接。 關(guān)關(guān) 于于 字字 符符 串串 的的 運(yùn)運(yùn) 算算52College of Computer Science & Technology, BUPTn 字符串字符串的逆用的逆用 表示。表示。 是字符是字符串串的倒置。的倒置。= b1b2bn = bnbn-1b2b1n 空串空串的逆還是的逆還是53College of Computer Science & Technology, BUPT字字 母母 表表 的的

40、冪冪 運(yùn)運(yùn) 算算 冪運(yùn)算冪運(yùn)算 Tn 用來(lái)表示用來(lái)表示 該字母表長(zhǎng)度為該字母表長(zhǎng)度為n的所有串的集的所有串的集合。設(shè)合。設(shè) T 為字母表，為字母表，n 為任意自然數(shù)，為任意自然數(shù)， 定義（定義（1） T0 = （2）設(shè)）設(shè) x Tn-1，a T， 則則a x Tn （3） Tn 中的元素只能由（中的元素只能由（1）和）和（2）生成）生成 閉包閉包 T* = T0 T1 T2 閉包閉包 T+ = T1 T2 T3 T* = T+ ， T+ = T* - - 54College of Computer Science & Technology, BUPT閉包的物理意義閉包的物理意義 T的星

41、號(hào)閉包的星號(hào)閉包T*：字母表T上的所有字符串和空串的集合。 T的正閉包的正閉包T+：字母表T上的所有字符串構(gòu)成的集合。T*= T+ 舉例舉例 設(shè)設(shè) T = 0，1 ，則則 T0 = ， T1 = 0，1 ， T2 = 00，01 ，10 ，11 ， T* = ，0，1，00，01 ，10 ，11， T+ = 0，1，00，01 ，10 ，11， 55College of Computer Science & Technology, BUPT語(yǔ) 言 （Languages） 概念概念 設(shè)設(shè) T 為字母表，則任何集合為字母表，則任何集合 L T* 是是字母字母表表T上的上的一個(gè)語(yǔ)言（一個(gè)語(yǔ)言

42、（language） 舉例舉例 - 英文單詞集英文單詞集 , English, , words , - C 語(yǔ)言程序集語(yǔ)言程序集 字母表？字母表？- 漢語(yǔ)成語(yǔ)集漢語(yǔ)成語(yǔ)集 , 馬到成功馬到成功, - 化學(xué)分子式集化學(xué)分子式集 , H2O, , NaCl , - any, 任意任意 56College of Computer Science & Technology, BUPT語(yǔ) 言 （Languages）舉例舉例：設(shè)：設(shè)T = a，b 則則 L1 = anbn | n1 L3 = bk | k 是質(zhì)數(shù)是質(zhì)數(shù) L2 = 只有一個(gè)空句子的語(yǔ)言只有一個(gè)空句子的語(yǔ)言 L4 = = 空語(yǔ)言空語(yǔ)言

43、 均為字母表均為字母表T上的語(yǔ)言。上的語(yǔ)言。由語(yǔ)言的定義知語(yǔ)言是集合，對(duì)于集合的運(yùn)算可由語(yǔ)言的定義知語(yǔ)言是集合，對(duì)于集合的運(yùn)算可應(yīng)用于對(duì)于語(yǔ)言的計(jì)算。如并，交，補(bǔ)，差。應(yīng)用于對(duì)于語(yǔ)言的計(jì)算。如并，交，補(bǔ)，差。57College of Computer Science & Technology, BUPT語(yǔ)言的基本運(yùn)算 語(yǔ)言的積：語(yǔ)言的積：兩個(gè)語(yǔ)言L1 和L2的積L1 L2是由L1和L2中的字符串連接所構(gòu)成的字符串的集合。即L1中所有字符串分別與L2中的字符串連接得到的集合。設(shè)T=a, b， L1和 L2是T上的語(yǔ)言。 L1 =ab, ba L2 =aa, bb則 L1 L2 =abaa

44、, abbb, baaa, babb L2 L1 =aaab, aaba, bbab, bbban L1 L2 L2 L1 語(yǔ)言的積不可交換。語(yǔ)言的積不可交換。58College of Computer Science & Technology, BUPT語(yǔ)言的基本運(yùn)算 語(yǔ)言的冪：語(yǔ)言的冪：語(yǔ)言的冪可歸納定義如下語(yǔ)言的冪可歸納定義如下: L0 = Ln = L Ln-1 = Ln-1 L n 1上例中，上例中，L12 =abab, abba, baab, baba L22 =aaaa, aabb, bbaa, bbbb 59College of Computer Science &am

45、p; Technology, BUPT第二節(jié) 文法n定義：所謂文法是用來(lái)定義語(yǔ)言的一個(gè)數(shù)學(xué)模型：所謂文法是用來(lái)定義語(yǔ)言的一個(gè)數(shù)學(xué)模型n表示語(yǔ)言的方法：n若語(yǔ)言若語(yǔ)言L是有限集合，可用是有限集合，可用列舉法n若若L是無(wú)限集合（集合中的每個(gè)元素有限長(zhǎng)度），是無(wú)限集合（集合中的每個(gè)元素有限長(zhǎng)度），用其他方法。用其他方法。n方法一：文法產(chǎn)生系統(tǒng)，由定義的文法規(guī)則產(chǎn)方法一：文法產(chǎn)生系統(tǒng)，由定義的文法規(guī)則產(chǎn)生出語(yǔ)言的每個(gè)句子生出語(yǔ)言的每個(gè)句子n方法二：機(jī)器識(shí)別系統(tǒng)：當(dāng)一個(gè)字符串能被一方法二：機(jī)器識(shí)別系統(tǒng)：當(dāng)一個(gè)字符串能被一個(gè)語(yǔ)言的識(shí)別系統(tǒng)接受，則這個(gè)字符串是該語(yǔ)個(gè)語(yǔ)言的識(shí)別系統(tǒng)接受，則這個(gè)字符串是該語(yǔ)言的

46、一個(gè)句子，否則不屬于該語(yǔ)言。言的一個(gè)句子，否則不屬于該語(yǔ)言。60College of Computer Science & Technology, BUPT元語(yǔ)言元語(yǔ)言n定義定義：描述語(yǔ)言的語(yǔ)言描述語(yǔ)言的語(yǔ)言例如：各種各樣的程序設(shè)計(jì)語(yǔ)言例如：各種各樣的程序設(shè)計(jì)語(yǔ)言n當(dāng)人們要解釋或討論程序設(shè)計(jì)語(yǔ)言本身時(shí)，又需要當(dāng)人們要解釋或討論程序設(shè)計(jì)語(yǔ)言本身時(shí)，又需要一種語(yǔ)言，被討論的語(yǔ)言叫做對(duì)象語(yǔ)言，即某種程一種語(yǔ)言，被討論的語(yǔ)言叫做對(duì)象語(yǔ)言，即某種程序設(shè)計(jì)語(yǔ)言，討論對(duì)象語(yǔ)言的語(yǔ)言稱為元語(yǔ)言序設(shè)計(jì)語(yǔ)言，討論對(duì)象語(yǔ)言的語(yǔ)言稱為元語(yǔ)言。61College of Computer Science &

47、; Technology, BUPTBNFBNF（巴科斯范式）巴科斯范式） BNF范式通常被作為討論某種程序設(shè)計(jì)語(yǔ)言語(yǔ)法的元語(yǔ)言n := 0|1|2|9 := “定義為”n := A|B|C|Z|a|b|z : = | | . n通過(guò)上述定義可知，所有以字母開頭的，由字母和數(shù)字組成的字符串都是標(biāo)識(shí)符。nBNF定義了一種語(yǔ)言，其中標(biāo)識(shí)符如上定義。nBNF描述它所定義的語(yǔ)言，為元語(yǔ)言。62College of Computer Science & Technology, BUPTn例如：漢語(yǔ)語(yǔ)法中定義了句子的結(jié)構(gòu)由主語(yǔ)、謂語(yǔ)、賓語(yǔ)組成。這里主謂賓只是描述了句子的結(jié)構(gòu)，并不是句子。而按照這種

48、結(jié)構(gòu)組成的建立在漢字上的字符串就是句子。如他是學(xué)生。n文法是一種元語(yǔ)言，一種方法，根據(jù)文法產(chǎn)文法是一種元語(yǔ)言，一種方法，根據(jù)文法產(chǎn)生出語(yǔ)言的句子。生出語(yǔ)言的句子。63College of Computer Science & Technology, BUPT三、Chomsky文法體系n例如：BNF := := := :=a|b|z|A|B|Z :=0|1|9將:= 改為表示可被代替用I, L, D分別表示標(biāo)識(shí)符、字母、數(shù)字;64College of Computer Science & Technology, BUPT三、Chomsky文法體系則上述表達(dá)式可以表示為則上述表達(dá)式

49、可以表示為 IL IIL IID La|b|.|z D0|1|.9這就是一個(gè)文法的生成式集合。這就是一個(gè)文法的生成式集合。65College of Computer Science & Technology, BUPT三、Chomsky文法體系nChomsky文法體系中，任何一種文法必須包含有兩個(gè)不同的有限符號(hào)的集合，即非終結(jié)符集合N和終結(jié)符集合T。一個(gè)形式規(guī)則的有限集合P（生成式集合），一個(gè)起始符S。nP中的生成式是用來(lái)產(chǎn)生語(yǔ)言句子的規(guī)則，而句子則是僅由終結(jié)符組成的字符串。這些字符串必須從一個(gè)起始符S開始，不斷使用P中的生成式而推導(dǎo)出來(lái)。n可見文法的核心是生成式的集合，它決定了語(yǔ)言中

50、句子的產(chǎn)生。66College of Computer Science & Technology, BUPT文法的形式定義n文法G是一個(gè)四元組G=(N，T，P，S)， 其中N 非終結(jié)符的有限集合T 終結(jié)符的有限集合 NT=P 形式為的生成式的有限集合。 且(NT)* N+ (NT)* (NT)*S 起始符 且S N。67College of Computer Science & Technology, BUPTn將上例用文法表示G=(N，T，P，S)N = I, L, DT = a, b, c,z, 0, 1, 9P = I, La, , D0, , D9S = I n文法是語(yǔ)

51、言的產(chǎn)生系統(tǒng)，研究怎樣構(gòu)造文法能產(chǎn)生出符合要求的句子。68College of Computer Science & Technology, BUPT四推導(dǎo)與句型1、直接推導(dǎo)設(shè)G =（N,T,P,S）是文法，若A是P中的生成式，和是（NT）*中的字符串，則有A= 稱A直接推導(dǎo)出，或說(shuō)是A的直接推導(dǎo)。69College of Computer Science & Technology, BUPTn設(shè)G = (N,T,P,S)是文法，、0、1n、都是（NT）*中的字符串，且=0、 =n，其中i直接推導(dǎo)出i+1 （0in）,則稱序列0=1=2=n是長(zhǎng)度為n的推導(dǎo)序列，而=0是長(zhǎng)度為0

52、的推導(dǎo)序列。n對(duì)推導(dǎo)出記為 ，若推導(dǎo)序列長(zhǎng)度大于0，則記為 。n推導(dǎo)序列的每一步，都產(chǎn)生一個(gè)字符串，這些字符串一般稱為句型。2、推導(dǎo)序列*G G 70College of Computer Science & Technology, BUPT3、句型和句子n句型字符串字符串是文法是文法G的句型，當(dāng)且僅當(dāng)?shù)木湫停?dāng)且僅當(dāng)S ，且且（NT）*。n 句子是是G的句子，當(dāng)且僅當(dāng)?shù)木渥?，?dāng)且僅當(dāng)S ,且且T*。（。（是由是由終結(jié)符組成的字符串）終結(jié)符組成的字符串）例：例：I =L =a I =IL =LL =zL =zbn句型包含句子*G *G 71College of Computer Sci

53、ence & Technology, BUPT4文法產(chǎn)生的語(yǔ)言由文法由文法G產(chǎn)生的語(yǔ)言記為產(chǎn)生的語(yǔ)言記為L(zhǎng)(G)。 L(G) = |T*且且S 或：或： L(G)中的一個(gè)字符串，必是由終結(jié)符中的一個(gè)字符串，必是由終結(jié)符組成的，并且是從起始符組成的，并且是從起始符S推導(dǎo)出來(lái)的。推導(dǎo)出來(lái)的。*G 72College of Computer Science & Technology, BUPT第三節(jié) Chomsky文法體系分類n文法文法 G = (N,T,P,S)； P: 其中其中 （NT）* N+（NT）* （NT）* 屬于屬于Chomsky文法體系文法體系n該體系對(duì)該體系對(duì)生成式

54、生成式的形式做了一些規(guī)定，分的形式做了一些規(guī)定，分為四類，即為四類，即0型、型、1型、型、2型、型、3型文法型文法n0型文法：無(wú)限制文法型文法：無(wú)限制文法對(duì)應(yīng)的語(yǔ)言：遞歸可枚舉語(yǔ)言，與圖靈機(jī)等價(jià)。73College of Computer Science & Technology, BUPT1型文法n也稱上下文有關(guān)文法（也稱上下文有關(guān)文法（CSG：Context-sensitive Grammar)生成式的形式為生成式的形式為，其中其中 |，（NT）+， （NT）*N+（NT）*n對(duì)應(yīng)的語(yǔ)言：上下文有關(guān)語(yǔ)言（對(duì)應(yīng)的語(yǔ)言：上下文有關(guān)語(yǔ)言（CSL：Context-sensitive Language)n若不考慮若不考慮，與線性有界自動(dòng)機(jī)（與線性有界自動(dòng)機(jī)（LBA, Linear Bounded Automaton）等價(jià)。等價(jià)。74College of Computer Science & Technology, BUPT1型文法語(yǔ)言限定約束：n左部的長(zhǎng)度小于右部左部的長(zhǎng)度小于右部n不含不含A-A-上下文有關(guān)語(yǔ)言CSL是對(duì)實(shí)際程序語(yǔ)言結(jié)構(gòu)的抽象：典型的這類語(yǔ)言結(jié)構(gòu)包括：變量的聲明與引用、變量的聲明與引用、過(guò)程調(diào)用時(shí)形參與實(shí)參的一致性檢查等