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

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

3、分析 - 形式系統形式系統 建模工具（狀態機建模工具（狀態機 ）- 抽象描述抽象描述 形式文法、形式表達式形式文法、形式表達式 課課 程程 性性 質質4College of Computer Science & Technology, BUPT相 關 課 程先修課程先修課程 - 離散數學離散數學（數理邏輯，集合論）（數理邏輯，集合論）- 計算機導論與程序設計、數據結構計算機導論與程序設計、數據結構 后續課程后續課程 - 編譯原理編譯原理 其它相關課程其它相關課程 模式識別、算法分析模式識別、算法分析 5College of Computer Science & Technolo

4、gy, BUPTn教材教材：形式語言與自動機形式語言與自動機 王柏王柏 楊娟楊娟 編著編著 北京郵電大學出版社北京郵電大學出版社 2003.16College of Computer Science & Technology, BUPT 經 典 參 考 書 書名書名 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） 清華大學出版社清華大學出版社 （影印版）（影印版） First Edition 中譯本中譯本自動機理論、語言和自動機理論、語言和計算導引計算導引 徐美瑞徐美瑞 等譯等譯 科學出版社，科學出版社，1990 John.E.Hopcroft,the Turing Awardwinner in 1986.7College of Computer Science & Technology, BUPT 其它參 考 書 自動機理論及其應用自動機理論及其應用 何成武何成武 科學出版社科學出版社19901990形式語言及其句法分析形式語言及

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

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

8、相似的學的形式化體系發展成為與現實生活相似的理論模型，從而提供一種通用結構來描述、理論模型，從而提供一種通用結構來描述、理解和解決問題。理解和解決問題。n計算機科學：是關于計算知識的有系統的整計算機科學：是關于計算知識的有系統的整體。體。10College of Computer Science & Technology, BUPT2、為什么學習形式語言與自動機為什么學習形式語言與自動機n計算機科學的兩個主要部分：n構成計算基礎的一些基本概念和模型；n設計計算系統(軟件和硬件)的工程技術（設計理論的應用）n本課程著重介紹第一部分（涉及到一些第二部分的應用），通過形式化技術對大家進行思維

9、訓練，為今后的學習打好理論基礎。11College of Computer Science & Technology, BUPT3 3、形式語言與自動機概述及應用、形式語言與自動機概述及應用n本門課程將圍繞著什么是形式語言、什么是自動機、以及形式語言和自動機的相互關系進行闡述。n核心內容 - 有限狀態自動機，正規語言，正規表達式- 上下文無關文法，上下文無關語言，下推 自動機- 圖靈機，計算問題分類12College of Computer Science & Technology, BUPT3.1 形式語言n什么是形式語言什么是形式語言n形式語言: 形式化描述的字母表上的字符

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

11、沒有國籍之一種語言，是一種通用語言，沒有國籍之分。分。n形式語言是某個字母表上的字符串的集合，形式語言是某個字母表上的字符串的集合，有一定的描述范圍。有一定的描述范圍。14College of Computer Science & Technology, BUPT為什么用形式語言為什么用形式語言n例例1： 漢語：漢語： 用數用數字、符號等形式化的東西來描述語言字、符號等形式化的東西來描述語言n我吃飯我吃飯 語法正確語法正確n我飯吃我飯吃 語法錯誤語法錯誤n飯吃我飯吃我 語法正確，語義錯誤語法正確，語義錯誤15College of Computer Science & Techn

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

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

14、流 n形式化非常重要19College of Computer Science & Technology, BUPT 3.2. 3.2. 自動機自動機n什么是自動機？具有離散輸入輸出的數學模型。包括：n輸入裝置讀頭+輸入帶n控制部件。 狀態轉移n存儲單元n大量通信軟件的基本工作機制都是有限狀態自動機。自動機理論在通信領域中的應用極為廣泛。20College of Computer Science & Technology, BUPT 3.2. 3.2. 自動機自動機n自動機接受一定的輸入，執行一定的動作，產生一定的結果。使用狀態遷移描述整個工作過程。n狀態狀態：一個標識，能區分

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

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

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

18、ge of Computer Science & Technology, BUPT自動機的分類n根據結構不同，自動機又可分為有限自動機，下推自動機，圖靈機等。n下推自動機可以看作是由一條輸入帶，一個有限控制器和一個下推棧組成。n基本圖靈機由一個具有讀寫頭的有限控制器和一條無限帶組成。n使用自動機，可以形式化的描述現實世界中的一些問題。27College of Computer Science & Technology, BUPT3 3.3 .3 形式語言與自動機的關系形式語言與自動機的關系n形式語言和自動機是密切相關的。形式語言 字符串自動機 字符串的識別系統n根據復雜程度可將

19、形式語言分類，根據自動機的接受能力、處理能力的不同也將自動機分類。二者之間具有較好的對應關系。28College of Computer Science & Technology, BUPT3 3.3 .3 形式語言與自動機的關系形式語言與自動機的關系29College of Computer Science & Technology, BUPT語言與有限自動機（Finite Automata） 設設 = 0, 1 ， L = w w 中至少有一個中至少有一個0 ， 如如 0011, 10, 110111 L, 而而11, , 1111 L。下圖是一個可接受該語言的有限狀態自動

20、機下圖是一個可接受該語言的有限狀態自動機 12Start0, 10130College of Computer Science & Technology, BUPT小結n文法是定義語言的一個數學模型，而自動機可看作是語言的識別系統。n通過對一些定理的證明，說明對于一個文法產生的語言，可以構造相應自動機接受該語言：一個自動機接受的語言，可以構造對應的文法產生該語言。一定類型的自動機和某種類型的文法具有等價性。 31College of Computer Science & Technology, BUPT課程內容及要求n課程內容： 書上二、三、四、五、六章。n要求：通過本課學習，

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

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

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

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

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

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

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

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

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

30、素生成新元素的規則 3 極小性限制極小性限制 / 申明集合中的元素只能由申明集合中的元素只能由 1、2 生成生成 43College of Computer Science & Technology, BUPT歸 納 證 明 與 結 構 歸 納 法結構歸納法結構歸納法 對于歸納（遞歸）定義的集合對于歸納（遞歸）定義的集合 S，欲證對于任意欲證對于任意x S，滿足性質滿足性質P(x). 1 基礎基礎（basis） / 若有直接定義若有直接定義 a S，則證明則證明 P(a) 2 歸納歸納（induction） / 若歸納定義中有規則若歸納定義中有規則 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 歸納定義歸納定義合法括號串的集合合法括號串的集合 S 1 基礎基礎 空串空串 S 2 歸納歸納 若若 x S ，則則 (x) S ； 若若 x,y S ，則則 xy S . 3 極小性限制極小性限制 S 中的元素只能由中的元素只能由 1、2 生成生成 (或：或： S是滿足是滿足1、2的最小集合的最小集合)

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

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

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

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

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

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

38、( x y ) z x（ y z ）- x x x - x y x + y 關關 于于 字字 符符 串串 的的 運運 算算51College of Computer Science & Technology, BUPT 其它其它 如如 取頭字符取頭字符，取尾部取尾部，子串匹配子串匹配 等等n 設設1, 2, 3是字母表是字母表T上的字符串，稱：上的字符串，稱：n1是字符串是字符串12的的前綴前綴，n2是字符串是字符串12的的后綴后綴，n2是字符串是字符串123的的子串子串。 n 空串是任何字符串的前綴，后綴及子串。空串是任何字符串的前綴，后綴及子串。n 例例：abc的前綴的前綴 a a

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

40、冪冪 運運 算算 冪運算冪運算 Tn 用來表示用來表示 該字母表長度為該字母表長度為n的所有串的集的所有串的集合。設合。設 T 為字母表，為字母表，n 為任意自然數，為任意自然數， 定義（定義（1） T0 = （2）設）設 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、號閉包的星號閉包T*：字母表T上的所有字符串和空串的集合。 T的正閉包的正閉包T+：字母表T上的所有字符串構成的集合。T*= T+ 舉例舉例 設設 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語 言 （Languages） 概念概念 設設 T 為字母表，則任何集合為字母表，則任何集合 L T* 是是字母字母表表T上的上的一個語言（一個語言

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

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

44、, abbb, baaa, babb L2 L1 =aaab, aaba, bbab, bbban L1 L2 L2 L1 語言的積不可交換。語言的積不可交換。58College of Computer Science & Technology, BUPT語言的基本運算 語言的冪：語言的冪：語言的冪可歸納定義如下語言的冪可歸納定義如下: 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第二節 文法n定義：所謂文法是用來定義語言的一個數學模型：所謂文法是用來定義語言的一個數學模型n表示語言的方法：n若語言若語言L是有限集合，可用是有限集合，可用列舉法n若若L是無限集合（集合中的每個元素有限長度），是無限集合（集合中的每個元素有限長度），用其他方法。用其他方法。n方法一：文法產生系統，由定義的文法規則產方法一：文法產生系統，由定義的文法規則產生出語言的每個句子生出語言的每個句子n方法二：機器識別系統：當一個字符串能被一方法二：機器識別系統：當一個字符串能被一個語言的識別系統接受，則這個字符串是該語個語言的識別系統接受，則這個字符串是該語言的

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

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

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

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

50、句子的產生。66College of Computer Science & Technology, BUPT文法的形式定義n文法G是一個四元組G=(N，T，P，S)， 其中N 非終結符的有限集合T 終結符的有限集合 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文法是語

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

52、的推導序列。n對推導出記為 ，若推導序列長度大于0，則記為 。n推導序列的每一步，都產生一個字符串，這些字符串一般稱為句型。2、推導序列*G G 70College of Computer Science & Technology, BUPT3、句型和句子n句型字符串字符串是文法是文法G的句型，當且僅當的句型，當且僅當S ，且且（NT）*。n 句子是是G的句子，當且僅當的句子，當且僅當S ,且且T*。（。（是由是由終結符組成的字符串）終結符組成的字符串）例：例：I =L =a I =IL =LL =zL =zbn句型包含句子*G *G 71College of Computer Sci

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

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