形式語言與自動機-緒論

1、12022-4-9College of Computer Science & Technology, BUPTFormal Languages and Automata 課程名稱課程名稱 形式語言與自動機形式語言與自動機 教師姓名教師姓名 楊娟楊娟（計算機學院（計算機學院 軟件工程中心）軟件工程中心） 電話電話 6228 3778 信箱信箱 助教助教 徐晨陽徐晨陽 彭爽彭爽 22022-4-9College of Computer Science & Technology, BUPT緒論緒論n 課程信息課程信息n 為什么學習形式語言與自動機為什么學習形式語言與自動機n 形式語言

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

3、分析計算的復雜性，算法分析 - 形式系統(tǒng)形式系統(tǒng) 建模工具（狀態(tài)機建模工具（狀態(tài)機 ）- 抽象描述抽象描述 形式文法、形式表達式形式文法、形式表達式 課課 程程 性性 質質42022-4-9College of Computer Science & Technology, BUPT相 關 課 程先修課程先修課程 - 離散數(shù)學離散數(shù)學（數(shù)理邏輯，集合論）（數(shù)理邏輯，集合論）- 計算機導論與程序設計、數(shù)據(jù)結構計算機導論與程序設計、數(shù)據(jù)結構 后續(xù)課程后續(xù)課程 - 編譯原理編譯原理 其它相關課程其它相關課程 模式識別、算法分析模式識別、算法分析 52022-4-9College of Comp

4、uter Science & Technology, BUPTn教材教材：形式語言與自動機形式語言與自動機 王柏王柏 楊娟楊娟 編著編著 北京郵電大學出版社北京郵電大學出版社 2003.162022-4-9College of Computer Science & Technology, BUPT 經(jīng) 典 參 考 書 書名書名 Introduction to Automata Theory, Languages, and Computation （Second Edition） 作者作者 John E. Hopcroft （Cornell） Rajeev Motwani （St

5、anford） Jefferey D. Ullman （Stanford） 出版社出版社 Addison Wesley （2001） 清華大學出版社清華大學出版社 （影印版）（影印版） First Edition 中譯本中譯本自動機理論、語言和自動機理論、語言和計算導引計算導引 徐美瑞徐美瑞 等譯等譯 科學出版社，科學出版社，1990 John.E.Hopcroft,the Turing Awardwinner in 1986.72022-4-9College of Computer Science & Technology, BUPT 其它參 考 書 自動機理論及其應用自動機理論及其

6、應用 何成武何成武 科學出版社科學出版社19901990形式語言及其句法分析形式語言及其句法分析 美美A.V. A.V. 阿霍阿霍 等等 科學出版社科學出版社1987 1987 形式語言形式語言 王兵山，吳兵王兵山，吳兵 編編 國防工業(yè)大學出版社，國防工業(yè)大學出版社，19881988 形式語言與自動機理論形式語言與自動機理論 蔣宗禮，姜守旭蔣宗禮，姜守旭. . 清華大學出版社，清華大學出版社，20032003形式語言與自動機形式語言與自動機 陳有祺陳有祺 編著編著 機械工業(yè)出版社，機械工業(yè)出版社，20082008 82022-4-9College of Computer Science &am

7、p; Technology, BUPT為什么學習形式語言與自動機n形式語言與自動機是計算機科學的基礎理論形式語言與自動機是計算機科學的基礎理論之一，是計算機學科的專業(yè)基礎課。之一，是計算機學科的專業(yè)基礎課。n在人工智能、電信領域等有廣泛的應用。在人工智能、電信領域等有廣泛的應用。n通過一些定理的證明和應用，對大家進行思通過一些定理的證明和應用，對大家進行思維訓練，從而為今后學習通信軟件，協(xié)議工維訓練，從而為今后學習通信軟件，協(xié)議工程，編譯技術，人工智能等內容提供理論基程，編譯技術，人工智能等內容提供理論基礎。礎。92022-4-9College of Computer Science &

8、; Technology, BUPTn對客觀世界的科學研究：目的在于把抽象數(shù)對客觀世界的科學研究：目的在于把抽象數(shù)學的形式化體系發(fā)展成為與現(xiàn)實生活相似的學的形式化體系發(fā)展成為與現(xiàn)實生活相似的理論模型，從而提供一種通用結構來描述、理論模型，從而提供一種通用結構來描述、理解和解決問題。理解和解決問題。n計算機科學：是關于計算知識的有系統(tǒng)的整計算機科學：是關于計算知識的有系統(tǒng)的整體。體。102022-4-9College of Computer Science & Technology, BUPTn計算機科學的兩個主要部分：n構成計算基礎的一些基本概念和模型；n設計計算系統(tǒng)(軟件和硬件)的工

9、程技術（設計理論的應用）n本課程著重介紹第一部分（涉及到一些第二部分的應用），通過形式化技術對大家進行思維訓練，為今后的學習打好理論基礎。n4 4種基本的專業(yè)能力種基本的專業(yè)能力n計算思維能力計算思維能力n算法的設計與分析能力算法的設計與分析能力n程序設計和實現(xiàn)能力程序設計和實現(xiàn)能力n計算機軟硬件系統(tǒng)的認知、分析、設計與應用能力計算機軟硬件系統(tǒng)的認知、分析、設計與應用能力n計算思維能力計算思維能力n邏輯思維能力和抽象思維能力邏輯思維能力和抽象思維能力n構造模型對問題進行形式化描述構造模型對問題進行形式化描述n理解和處理形式模型理解和處理形式模型112022-4-9122022-4-9Colle

10、ge of Computer Science & Technology, BUPT2022-4-913n能力能力n培養(yǎng)學生的形式化描述和抽象思維能力。培養(yǎng)學生的形式化描述和抽象思維能力。n使學生了解和初步掌握使學生了解和初步掌握“問題、形式化描述、自問題、形式化描述、自動化（計算機化）動化（計算機化）”這一最典型的計算機問題求這一最典型的計算機問題求解思路。解思路。 形式語言與自動機概述及應用n本門課程將圍繞著什么是形式語言、什么是自動機、以及形式語言和自動機的相互關系進行闡述。n核心內容核心內容n有限狀態(tài)自動機，正規(guī)語言，正規(guī)表達式有限狀態(tài)自動機，正規(guī)語言，正規(guī)表達式n上下文無關文法

11、，上下文無關語言，下推自動機上下文無關文法，上下文無關語言，下推自動機n 圖靈機，計算問題分類圖靈機，計算問題分類142022-4-9College of Computer Science & Technology, BUPT152022-4-9College of Computer Science & Technology, BUPT1形式語言n什么是形式語言什么是形式語言n形式語言: 形式化描述的字母表上的字符串的集形式化描述的字母表上的字符串的集合。合。n字母表：字符的有限集合。ne.g.：26個英文字母構成的字母表。n字符串：字母表中的字符構成的有限序列。ne.g. h

12、ello, afjhkfyu 162022-4-9College of Computer Science & Technology, BUPT為什么用形式語言為什么用形式語言n自然語言自然語言：人們平時說話時所使用的一種語：人們平時說話時所使用的一種語言，不同的國家和民族有著不同的語言。言，不同的國家和民族有著不同的語言。n形式語言形式語言n通過人們公認的符號，表達方式所描述的通過人們公認的符號，表達方式所描述的一種語言，是一種通用語言，沒有國籍之一種語言，是一種通用語言，沒有國籍之分。分。n形式語言是某個字母表上的字符串的集合，形式語言是某個字母表上的字符串的集合，有一定的描述范圍。

13、有一定的描述范圍。172022-4-9College of Computer Science & Technology, BUPTn例例1： 漢語：漢語： 用數(shù)用數(shù)字、符號等形式化的東西來描述語言字、符號等形式化的東西來描述語言n我吃飯我吃飯 語法正確語法正確n我飯吃我飯吃 語法錯誤語法錯誤n飯吃我飯吃我 語法正確，語義錯誤語法正確，語義錯誤182022-4-9College of Computer Science & Technology, BUPTn例2：T為PASCAL語言所用的全部符號的集合。n正確的PASCAL程序就是T上的語言。n例3：在字母表T=a上，L = a

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

15、通信協(xié)議、通信軟件等多個領域n在計算機理論科學方面： 是可計算理論（算法在有限步驟內求得解、算法復雜性、停機問題、）、定理自動證明、程序轉換（程序自動生成）、模式識別等的基礎。212022-4-9College of Computer Science & Technology, BUPTn比爾.蓋茨：人類計算的未來是讓計算機能夠看、聽、學，能用自然語言與人類交流 n形式化非常重要n例1：微軟對聯(lián)軟件網(wǎng)址：網(wǎng)址：http:/ of Computer Science & Technology, BUPT圖靈測試圖靈測試 (1)n問：請給我寫出有關“第四號橋”主題的十四行詩。n答：不

16、要問我這道題，我從來不會寫詩。n問：34957加70764等于多少？n答：（停30秒后）105721n問：你會下國際象棋嗎？n答：是的。n問：我在我的K1處有棋子K；你僅在K6處有棋子K，在R1處有棋子R?，F(xiàn)在輪到你走，你應該下那步棋？n答：（停15秒鐘后）棋子R走到R8處，將軍！232022-4-9College of Computer Science & Technology, BUPT圖靈測試圖靈測試 (2)n問：你會下國際象棋嗎？n答：是的。n問：你會下國際象棋嗎？n答：是的。n問：請再次回答，你會下國際象棋嗎？n答：是的。242022-4-9College of Comput

17、er Science & Technology, BUPT圖靈測試圖靈測試 (3)n問：你會下國際象棋嗎？n答：是的。n問：你會下國際象棋嗎？n答：是的，我不是已經(jīng)說過了嗎？n問：請再次回答，你會下國際象棋嗎？n答：你煩不煩，干嘛老提同樣的問題。25College of Computer Science & Technology, BUPT在線圖靈測試網(wǎng)址在線圖靈測試網(wǎng)址nElbothttp:/ of Computer Science & Technology, BUPT 2. 自動機自動機n什么是自動機？具有離散輸入輸出的數(shù)學模型。n大量通信軟件的基本工作機制都是有限

18、狀態(tài)自動機。自動機理論在通信領域中的應用極為廣泛。272022-4-9College of Computer Science & Technology, BUPTn自動機接受一定的輸入，執(zhí)行一定的動作，產(chǎn)生一定的結果。使用狀態(tài)遷移描述整個工作過程。n狀態(tài)狀態(tài)：一個標識，能區(qū)分自動機在不同時刻的狀況。有限狀態(tài)系統(tǒng)具有任意有限數(shù)目的內部“狀態(tài)”n自動機的本質自動機的本質：根據(jù)狀態(tài)、輸入和規(guī)則決定下一個狀態(tài)狀態(tài)狀態(tài) 輸入（激勵）輸入（激勵） 規(guī)則規(guī)則 狀態(tài)遷移狀態(tài)遷移282022-4-9College of Computer Science & Technology, BUPT為什么

19、叫自動機？為什么叫自動機？n可能的狀態(tài)、運行的規(guī)則都是事先確定的。一旦開始運行，就按照事先確定的規(guī)則工作，因此叫“自動機”。n有限自動機可以認為是由一個帶有讀頭的有限控制器和一條寫有字符的輸入帶組成。292022-4-9College of Computer Science & Technology, BUPTn例1：打電話 (自動機在通信領域的應用)。 在一次呼叫中，從建立連接到通話完畢，要經(jīng)歷摘機，撥號，應答，進行通話等過程，可以分別用五個狀態(tài)來表示。q0q0q1q1q2q2q3q3q4q4摘機摘機收到撥號音收到撥號音撥號撥號收應答信號收應答信號掛機掛機收齊號碼收齊號碼q0:q0:

20、空閑狀態(tài)空閑狀態(tài)q1:q1:等待撥號狀態(tài)等待撥號狀態(tài)q2:q2:可以撥號狀態(tài)可以撥號狀態(tài)q3:q3:等待應答狀態(tài)等待應答狀態(tài)q4:q4:通話狀態(tài)通話狀態(tài)302022-4-9College of Computer Science & Technology, BUPTn例2：串口通信 兩臺微機通過串口通信, 需在兩臺機器間建立好連接后，才可以傳遞數(shù)據(jù)，可以使用有限狀態(tài)自動機，描述串口通信的狀態(tài)。傳輸數(shù)據(jù)收到應答斷開連接連接請求q0q1q2312022-4-9College of Computer Science & Technology, BUPTn根據(jù)結構不同，自動機又可分為有限

21、自動機，下推自動機，圖靈機等。n下推自動機可以看作是由一條輸入帶，一個有限控制器和一個下推棧組成。n基本圖靈機由一個具有讀寫頭的有限控制器和一條無限帶組成。n使用自動機，可以形式化的描述現(xiàn)實世界中的一些問題。322022-4-9College of Computer Science & Technology, BUPT3形式語言與自動機的關系形式語言與自動機的關系n形式語言和自動機是密切相關的。形式語言 字符串自動機 字符串的識別系統(tǒng)n根據(jù)復雜程度可將形式語言分類，根據(jù)自動機的接受能力、處理能力的不同也將自動機分類。二者之間具有較好的對應關系。332022-4-9College of

22、Computer Science & Technology, BUPT342022-4-9College of Computer Science & Technology, BUPT語言與有限自動機（Finite Automata） 設設 = 0, 1 ， L = w w 中至少有一個中至少有一個0 ， 如如 0011, 10, 110111 L, 而而11, , 1111 L。下圖是一個可接受該語言的有限狀態(tài)自動機下圖是一個可接受該語言的有限狀態(tài)自動機 12Start0, 101352022-4-9College of Computer Science & Techn

23、ology, BUPT小結n文法是定義語言的一個數(shù)學模型，而自動機可看作是語言的識別系統(tǒng)。n通過對一些定理的證明，說明對于一個文法產(chǎn)生的語言，可以構造相應自動機接受該語言：一個自動機接受的語言，可以構造對應的文法產(chǎn)生該語言。一定類型的自動機和某種類型的文法具有等價性。 362022-4-9College of Computer Science & Technology, BUPT課程內容及要求n課程內容： 書上二、三、四、五章。n要求：通過本課學習，要求同學們掌握形式化描述方法，建立起形式語言與自動機的概念，并能在實際中加以應用。n通過對定理的證明，對同學們進行思維訓練，并掌握一定的證

24、明方法。372022-4-9College of Computer Science & Technology, BUPT證 明 技 術* 基本證明方法基本證明方法 歸納證明技術歸納證明技術* 引自清華大學計算機系軟件技術研究所王生原老師課件引自清華大學計算機系軟件技術研究所王生原老師課件382022-4-9College of Computer Science & Technology, BUPT演 繹 證 明 概念概念 一個一個 證明證明（proof）是命題的序列，是命題的序列，其中的每一個命題或者是已知的命題，或者是其中的每一個命題或者是已知的命題，或者是由前面出現(xiàn)過的命題

25、使用邏輯公理和規(guī)則得出由前面出現(xiàn)過的命題使用邏輯公理和規(guī)則得出. 已知的命題集合稱為已知的命題集合稱為假設假設（hypothesis）或或前前提提（premise），），最后一個命題稱為該前提的最后一個命題稱為該前提的結論結論（conclusion）. 392022-4-9College of Computer Science & Technology, BUPT“If Then”命題命題 證明方法證明方法 把把 If 部分作為已知的命題，把部分作為已知的命題，把 Then 部分作部分作為結論為結論. 舉例舉例 如果如果x+y=1，那么那么x2-y2=x-y. 證明證明:1 x2-y2

26、 = (x+y)(x-y) / 數(shù)學數(shù)學公理公理2 (x+y) = 1 / 已知已知x2-y2 = x-y / 由由1、2 和算術性質推出和算術性質推出402022-4-9College 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. 412022-4-9College of Computer Science & Technology,

27、BUPT有關集合的命題有關集合的命題 設設 R, S 為集合為集合. 欲證欲證 R S， 可證明如下命題：可證明如下命題： if x R then x S 欲證欲證 R = S， 可分別證明如下兩個命題：可分別證明如下兩個命題： 1 if x R then x S 2 if x S then x R422022-4-9College of Computer Science & Technology, BUPT原命題的逆否命題原命題的逆否命題 有時，證明原命題的逆否有時，證明原命題的逆否(contrapositive) 命題更加方便命題更加方便. 欲證欲證 if A then B ， 可

28、證明如下命題：可證明如下命題： if not B then not A432022-4-9College of Computer Science & Technology, BUPT反證法反證法 反證（反證（proof by contradiction） 欲證欲證 if H then C ，可以把可以把 H 和和 not C 都作為已知的命題，把任何一個矛盾都作為已知的命題，把任何一個矛盾( contradiction )命題作為新的結論命題作為新的結論.442022-4-9College of Computer Science & Technology, BUPT舉例證明或否

29、證舉例證明或否證 舉例證明存在量化的命題舉例證明存在量化的命題 如命題：存在整數(shù)如命題：存在整數(shù) a，滿足滿足 a2 = 2a. 證明證明: 取取 a = 2. ，滿足滿足 a2 = 2a. 舉反例否定全稱量化的命題舉反例否定全稱量化的命題 如命題：所有整數(shù)如命題：所有整數(shù) a，都滿足都滿足 a2=2a. 否證否證: 取取 a = 1. ，不滿足不滿足 a2 = 2a. 452022-4-9College of Computer Science & Technology, BUPT 集合的歸納定義集合的歸納定義 由由 3 部分構成：部分構成： 1 基礎基礎（basis） / / 直接定

30、義集合中的元素（至少直接定義集合中的元素（至少1個）個） 2 歸納歸納（induction）/ / 從已知元素生成新元素的規(guī)則從已知元素生成新元素的規(guī)則 3 極小性限制極小性限制 / / 申明集合中的元素只能由申明集合中的元素只能由 1、2 生成生成 結構歸納法結構歸納法 對于歸納定義的集合對于歸納定義的集合 S，欲證對于任意欲證對于任意x S，滿足性質滿足性質P(x). 1 基礎基礎（basis） / / 若有直接定義若有直接定義 a S，則證明則證明 P(a) 2 歸納歸納（induction） / / 若歸納定義中有規(guī)則若歸納定義中有規(guī)則 if a1, a2, , an S then f (a1, a2, , an ) S ，則證明則證明 if P( a1 ), P( a2 ), , P( an ) then P( f (a1, a2, , an )