《形式語言與自動機》1緒論

1、1College of Computer Science & Technology, BUPTFormal Languages and Automata 課程名稱課程名稱 形式語言與自動機形式語言與自動機 教師姓名教師姓名 王柏王柏 （計算機學(xué)院（計算機學(xué)院 通信軟件工程中心）通信軟件工程中心） 電話電話 6228 3774 Office 教三樓教三樓 616 信箱信箱 2College of Computer Science & Technology, BUPT緒論緒論n 課程信息課程信息n 為什么學(xué)習(xí)形式語言與自動機為什么學(xué)習(xí)形式語言與自動機n 形式語言與自動機概述及應(yīng)用形式語言與自動機概

2、述及應(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) - 計算模型計算模型 計算機（不）能夠做什么計算機（不）能夠做什么 - 問題分類問題分類 計算的復(fù)雜性，算法分析計算的復(fù)雜性，算法分析 - 形式系統(tǒng)形式系統(tǒng) 建模工具（狀態(tài)

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

4、機 王柏王柏 楊娟楊娟 編著編著 北京郵電大學(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 （Stanford） 出版社出版社 Addison Wesley （2001） 清

5、華大學(xué)出版社清華大學(xué)出版社 （影印版）（影印版） First Edition 中譯本中譯本自動機理論、語言和計自動機理論、語言和計算導(dǎo)引算導(dǎo)引 徐美瑞徐美瑞 等譯等譯 科學(xué)出版社，科學(xué)出版社，1990 John.E.Hopcroft,the Turing Awardwinner in 1986.7College of Computer Science & Technology, BUPT 其它參 考 書 計算理論導(dǎo)引計算理論導(dǎo)引 ( (有新版本有新版本) ) 美美 M.Sipser M.Sipser 張立昂張立昂 等譯等譯 機工社機工社 20002000形式語言及其句法分析形式語言及其句法分析

6、 美美A.V. A.V. 阿霍阿霍 等等 科學(xué)出版社科學(xué)出版社1987 1987 形式語言與自動機形式語言與自動機 陳有祺陳有祺 編編 機工社，機工社，20082008 形式語言與自動機形式語言與自動機 蔣宗禮蔣宗禮 編著編著 清華大學(xué)出版社，清華大學(xué)出版社，20032003 8College of Computer Science & Technology, BUPT為什么學(xué)習(xí)形式語言與自動機n形式語言與自動機是計算機科學(xué)的基礎(chǔ)理論形式語言與自動機是計算機科學(xué)的基礎(chǔ)理論之一，是計算機學(xué)科的專業(yè)基礎(chǔ)課。之一，是計算機學(xué)科的專業(yè)基礎(chǔ)課。n在人工智能、電信領(lǐng)域等有廣泛的應(yīng)用。在人工智能、電信領(lǐng)域等

7、有廣泛的應(yīng)用。n通過一些定理的證明和應(yīng)用，對大家進(jìn)行思通過一些定理的證明和應(yīng)用，對大家進(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, BUPTn對客觀世界的科學(xué)研究：目的在于把抽象數(shù)對客觀世界的科學(xué)研究：目的在于把抽象數(shù)學(xué)的形式化體系發(fā)展成為與現(xiàn)實生活相似的學(xué)的形式化體系發(fā)展成為與現(xiàn)實生活相似的理論模型，從而提供一種通用結(jié)構(gòu)來描述、理論模型，從而提供一種通用結(jié)構(gòu)來描述、理解和解決問題。理解和解

8、決問題。n計算機科學(xué)：是關(guān)于計算知識的有系統(tǒng)的整計算機科學(xué)：是關(guān)于計算知識的有系統(tǒng)的整體。體。10College of Computer Science & Technology, BUPTn計算機科學(xué)的兩個主要部分：n構(gòu)成計算基礎(chǔ)的一些基本概念和模型；n設(shè)計計算系統(tǒng)(軟件和硬件)的工程技術(shù)（設(shè)計理論的應(yīng)用）n本課程著重介紹第一部分（涉及到一些第二部分的應(yīng)用），通過形式化技術(shù)對大家進(jìn)行思維訓(xùn)練，為今后的學(xué)習(xí)打好理論基礎(chǔ)。n4 4種基本的專業(yè)能力種基本的專業(yè)能力n計算思維能力計算思維能力n算法的設(shè)計與分析能力算法的設(shè)計與分析能力n程序設(shè)計和實現(xiàn)能力程序設(shè)計和實現(xiàn)能力n計算機軟硬件系統(tǒng)的認(rèn)知、分析

9、、設(shè)計與應(yīng)用能力計算機軟硬件系統(tǒng)的認(rèn)知、分析、設(shè)計與應(yīng)用能力n計算思維能力計算思維能力n邏輯思維能力和抽象思維能力邏輯思維能力和抽象思維能力n構(gòu)造模型對問題進(jìn)行形式化描述構(gòu)造模型對問題進(jìn)行形式化描述n理解和處理形式模型理解和處理形式模型112022-7-4122022-7-4College of Computer Science & Technology, BUPT2022-7-413n能力能力n培養(yǎng)學(xué)生的形式化描述和抽象思維能力。培養(yǎng)學(xué)生的形式化描述和抽象思維能力。n使學(xué)生了解和初步掌握使學(xué)生了解和初步掌握“問題、形式化描述、自問題、形式化描述、自動化（計算機化）動化（計算機化）”這一最典型

10、的計算機問題求這一最典型的計算機問題求解思路。解思路。 14College of Computer Science & Technology, BUPT形式語言與自動機概述及應(yīng)用n本門課程將圍繞著什么是形式語言、什么是自動機、以及形式語言和自動機的相互關(guān)系進(jìn)行闡述。n核心內(nèi)容 - 有限狀態(tài)自動機，正規(guī)語言，正規(guī)表達(dá)式- 上下文無關(guān)文法，上下文無關(guān)語言，下推 自動機- 圖靈機，計算問題分類15College of Computer Science & Technology, BUPT1形式語言n什么是形式語言什么是形式語言n形式語言: 形式化描述的字母表上的字符串的集形式化描述的字母表上的字符串

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

12、籍之分。分。n形式語言是某個字母表上的字符串的集合，形式語言是某個字母表上的字符串的集合，有一定的描述范圍。有一定的描述范圍。17College of Computer Science & Technology, BUPTn例例1： 漢語：漢語： 用數(shù)用數(shù)字、符號等形式化的東西來描述語言字、符號等形式化的東西來描述語言n我吃飯我吃飯 語法正確語法正確n我飯吃我飯吃 語法錯誤語法錯誤n飯吃我飯吃我 語法正確，語義錯誤語法正確，語義錯誤18College of Computer Science & Technology, BUPTn例2：T為PASCAL語言所用的全部符號的集合。n正確的PASCA

13、L程序就是T上的語言。n例3：在字母表T=a上，L = a 2n+1 | n =0 n表示任意一對aa (包括0對) 后跟一個a的字符串。（即含有奇數(shù)個a的字符串。）19College of Computer Science & Technology, BUPTn形式語言的最初起因： 語言學(xué)家（Chomsky）想用一套形式化方法來描述語言。n形式語言在自然語言研究中起步，在計算機科學(xué)中得到廣泛應(yīng)用。n最初的應(yīng)用：編譯 讓計算機按照語法規(guī)則將高級語言方便地翻譯成機器語言。20College of Computer Science & Technology, BUPTn現(xiàn)在： 已廣泛應(yīng)用在人工智能

14、、圖象處理、通信協(xié)議、通信軟件等多個領(lǐng)域n在計算機理論科學(xué)方面： 是可計算理論（算法在有限步驟內(nèi)求得解、算法復(fù)雜性、停機問題、）、定理自動證明、程序轉(zhuǎn)換（程序自動生成）、模式識別等的基礎(chǔ)。21College of Computer Science & Technology, BUPTn比爾.蓋茨：人類計算的未來是讓計算機能夠看、聽、學(xué)，能用自然語言與人類交流 n形式化非常重要n例1：微軟對聯(lián)軟件n例2：圖靈測試22College of Computer Science & Technology, BUPT高級認(rèn)知活動:對聯(lián)軟件n比爾.蓋茨：人類計算的未來是讓計算機能夠看、聽、學(xué)，能用自然語言與

15、人類交流 n形式化非常重要n唐詩宋詞三百首：41850首，首，8萬句，近萬句，近35萬字萬字n微軟對聯(lián)軟件：微軟亞洲研究院自然語言計算組研發(fā)的計算機自動對聯(lián)系統(tǒng)。利用從唐詩宋詞大數(shù)據(jù)中學(xué)習(xí)到的概率模型，當(dāng)用戶給定上聯(lián)，能自動提供若干下聯(lián)； 當(dāng)用戶確定一副對聯(lián)，能生成若干四字橫批。網(wǎng)址：網(wǎng)址：http:/ of Computer Science & Technology, BUPT圖靈測試圖靈測試 (1)n問：請給我寫出有關(guān)“第四號橋”主題的十四行詩。n答：不要問我這道題，我從來不會寫詩。n問：34957加70764等于多少？n答：（停30秒后）105721n問：你會下國際象棋嗎？n答：是的。n

16、問：我在我的K1處有棋子K；你僅在K6處有棋子K，在R1處有棋子R?，F(xiàn)在輪到你走，你應(yīng)該下那步棋？n答：（停15秒鐘后）棋子R走到R8處，將軍！24College of Computer Science & Technology, BUPT圖靈測試圖靈測試 (2)n問：你會下國際象棋嗎？n答：是的。n問：你會下國際象棋嗎？n答：是的。n問：請再次回答，你會下國際象棋嗎？n答：是的。25College of Computer Science & Technology, BUPT圖靈測試圖靈測試 (3)n問：你會下國際象棋嗎？n答：是的。n問：你會下國際象棋嗎？n答：是的，我不是已經(jīng)說過了嗎？n問

17、：請再次回答，你會下國際象棋嗎？n答：你煩不煩，干嘛老提同樣的問題。26College of Computer Science & Technology, BUPT在線圖靈測試網(wǎng)址在線圖靈測試網(wǎng)址nElbothttp:/ of Computer Science & Technology, BUPT 2. 自動機自動機n什么是自動機？具有離散輸入輸出的數(shù)學(xué)模型。n大量通信軟件的基本工作機制都是有限狀態(tài)自動機。自動機理論在通信領(lǐng)域中的應(yīng)用極為廣泛。28College of Computer Science & Technology, BUPTn自動機接受一定的輸入，執(zhí)行一定的動作，產(chǎn)生一定的結(jié)果。

18、使用狀態(tài)遷移描述整個工作過程。n狀態(tài)狀態(tài)：一個標(biāo)識，能區(qū)分自動機在不同時刻的狀況。有限狀態(tài)系統(tǒng)具有任意有限數(shù)目的內(nèi)部“狀態(tài)”n自動機的本質(zhì)自動機的本質(zhì)：根據(jù)狀態(tài)、輸入和規(guī)則決定下一個狀態(tài)狀態(tài)狀態(tài) 輸入（激勵）輸入（激勵） 規(guī)則規(guī)則 狀態(tài)遷移狀態(tài)遷移 例：商場自動門例：商場自動門29College of Computer Science & Technology, BUPT為什么叫自動機？為什么叫自動機？n可能的狀態(tài)、運行的規(guī)則都是事先確定的。一旦開始運行，就按照事先確定的規(guī)則工作，因此叫“自動機”。n有限自動機可以認(rèn)為是由一個帶有讀頭的有限控制器和一條寫有字符的輸入帶組成。30College

19、of Computer Science & Technology, BUPTn例1：打電話 (自動機在通信領(lǐng)域的應(yīng)用)。 在一次呼叫中，從建立連接到通話完畢，要經(jīng)歷摘機，撥號，應(yīng)答，進(jìn)行通話等過程，可以分別用四個狀態(tài)來表示。q0q0q1q1q2q2q3q3q4q4摘機摘機收到撥號音收到撥號音撥號撥號收應(yīng)答信號收應(yīng)答信號掛機掛機收齊號碼收齊號碼q0:q0:空閑狀態(tài)空閑狀態(tài)q1:q1:等待撥號狀態(tài)等待撥號狀態(tài)q2:q2:可以撥號狀態(tài)可以撥號狀態(tài)q3:q3:等待應(yīng)答狀態(tài)等待應(yīng)答狀態(tài)q4:q4:通話狀態(tài)通話狀態(tài)31College of Computer Science & Technology, BU

20、PTn例2：串口通信 兩臺微機通過串口通信, 需在兩臺機器間建立好連接后，才可以傳遞數(shù)據(jù)，可以使用有限狀態(tài)自動機，描述串口通信的狀態(tài)。傳輸數(shù)據(jù)收到應(yīng)答斷開連接連接請求q0q1q2q0：空閑q1：等待應(yīng)答q2：傳輸狀態(tài)32College of Computer Science & Technology, BUPTn根據(jù)結(jié)構(gòu)不同，自動機又可分為有限自動機，下推自動機，圖靈機等。n下推自動機可以看作是由一條輸入帶，一個有限控制器和一個下推棧組成。n基本圖靈機由一個具有讀寫頭的有限控制器和一條無限帶組成。n使用自動機，可以形式化的描述現(xiàn)實世界中的一些問題。33College of Computer S

21、cience & Technology, BUPT3形式語言與自動機的關(guān)系形式語言與自動機的關(guān)系n形式語言和自動機是密切相關(guān)的。形式語言 字符串自動機 字符串的識別系統(tǒng)n根據(jù)復(fù)雜程度可將形式語言分類，根據(jù)自動機的接受能力、處理能力的不同也將自動機分類。二者之間具有較好的對應(yīng)關(guān)系。34College of Computer Science & Technology, BUPT35College of Computer Science & Technology, BUPT語言與有限自動機（Finite Automata） 設(shè)設(shè) T = 0, 1 ， L = 中至少有一個中至少有一個0 ， 如如 0

22、011, 10, 110111 L, 而而11, , 1111 L。下圖是一個可接受該語言的有限狀態(tài)自動機下圖是一個可接受該語言的有限狀態(tài)自動機 12Start0, 10136College of Computer Science & Technology, BUPT小結(jié)n文法是定義語言的一個數(shù)學(xué)模型，而自動機可看作是語言的識別系統(tǒng)。n通過對一些定理的證明，說明對于一個文法產(chǎn)生的語言，可以構(gòu)造相應(yīng)自動機接受該語言：一個自動機接受的語言，可以構(gòu)造對應(yīng)的文法產(chǎn)生該語言。一定類型的自動機和某種類型的文法具有等價性。 37College of Computer Science & Technology

23、, BUPT課程內(nèi)容及要求n課程內(nèi)容： 書上二、三、四、五、六章。n要求：通過本課學(xué)習(xí)，要求同學(xué)們掌握形式化描述方法，建立起形式語言與自動機的概念，并能在實際中加以應(yīng)用。n通過對定理的證明，對同學(xué)們進(jìn)行思維訓(xùn)練，并掌握一定的證明方法。38College of Computer Science & Technology, BUPT第一次作業(yè)n任選（或自行發(fā)現(xiàn)）一個網(wǎng)址，上網(wǎng)試驗圖靈測試。給出一串問答的例子（要求中英文對照，3月20日以前由小班班長/學(xué)委收齊上交老師）。n作業(yè)要求：首先說明選的是哪個網(wǎng)址，注明“問”“答”。n文件名為：學(xué)號-姓名-圖靈測試 （不合規(guī)格的拒收）n收件人： 39Coll

24、ege of Computer Science & Technology, BUPT證 明 技 術(shù)* 基本證明方法基本證明方法 歸納證明技術(shù)歸納證明技術(shù)* 引自清華大學(xué)計算機系軟件技術(shù)研究所王生原老師課件引自清華大學(xué)計算機系軟件技術(shù)研究所王生原老師課件40College of Computer Science & Technology, BUPT演 繹 證 明 概念概念 一個一個 證明證明（proof）是命題的序列，是命題的序列，其中的每一個命題或者是已知的命題，或者是其中的每一個命題或者是已知的命題，或者是由前面出現(xiàn)過的命題使用邏輯公理和規(guī)則得出由前面出現(xiàn)過的命題使用邏輯公理和規(guī)則得出. 已

25、知的命題集合稱為已知的命題集合稱為假設(shè)假設(shè)（hypothesis）或或前前提提（premise），），最后一個命最后一個命 題稱為該前提的題稱為該前提的結(jié)論結(jié)論（conclusion）. 41College of Computer Science & Technology, BUPT“If Then”命題命題 證明方法證明方法 把把 If 部分作為已知的命題，把部分作為已知的命題，把 Then 部分作部分作為結(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-

26、y2 = x-y / 由由1、2 和算術(shù)性質(zhì)推出和算術(shù)性質(zhì)推出 42College of Computer Science & Technology, BUPT“If - And - Only - If ”命題命題 欲證欲證 A if and only if B， 可分別證明如下兩個命題：可分別證明如下兩個命題： 1 if A then B， 2 if B then A. 43College of Computer Science & Technology, BUPT有關(guān)集合的命題有關(guān)集合的命題 設(shè)設(shè) R, S 為集合為集合. 欲證欲證 R S， 可證明如下命題：可證明如下命題： if x R

27、 then x S 欲證欲證 R = S， 可分別證明如下兩個命題：可分別證明如下兩個命題： 1 if x R then x S 2 if x S then x R44College of Computer Science & Technology, BUPT原命題的逆否命題原命題的逆否命題 有時，證明原命題的逆否有時，證明原命題的逆否(contrapositive) 命題更加方便命題更加方便. 欲證欲證 if A then B ， 可證明如下命題：可證明如下命題： if not B then not A45College of Computer Science & Technology, B

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

29、化的命題舉反例否定全稱量化的命題 如命題：所有整數(shù)如命題：所有整數(shù) a，都滿足都滿足 a2=2a. 否證否證: 取取 a = 1. ，不滿足不滿足 a2 = 2a. 47College of Computer Science & Technology, BUPT 集合的歸納定義集合的歸納定義 由由 3 部分構(gòu)成：部分構(gòu)成： 1 基礎(chǔ)基礎(chǔ)（basis） / / 直接定義集合中的元素（至少直接定義集合中的元素（至少1個）個） 2 歸納歸納（induction）/ / 從已知元素生成新元素的規(guī)則從已知元素生成新元素的規(guī)則 3 極小性限制極小性限制 / / 申明集合中的元素只能由申明集合中的元素只能由 1、2 生成生成 結(jié)構(gòu)歸納法結(jié)構(gòu)歸納法 對于歸納定義的集合對于歸納定義的集合 S，欲證對于任意欲證對于任意x S，滿足性質(zhì)滿足性質(zhì)P(x). 1 基礎(chǔ)基礎(chǔ)（basis） / / 若有直接定義若有直接定