形式語言與自動機(jī)week1introduction

1、Formal Languages and Automata 課程名稱 形式語言與自動機(jī) 教師姓名 電話 6228 3774 Office 教三樓 616 信箱 1緒論 課程信息 為什么學(xué)習(xí)形式語言與自動機(jī) 形式語言與自動機(jī)概述及應(yīng)用 課程內(nèi)容及要求2 專業(yè)基礎(chǔ)課 上世紀(jì) 60 年代末、70年代初，研究的高峰 之后，向應(yīng)用領(lǐng)域滲透，研究生課程 近幾年，本科階段的專業(yè)基礎(chǔ)課 專業(yè)工作者必須的理論素養(yǎng) 計算模型 計算機(jī)（不）能夠做什么 問題分類 計算的復(fù)雜性，算法分析 形式系統(tǒng) 建模工具（狀態(tài)機(jī) ） 抽象描述 形式文法、形式表達(dá)式 課 程 性 質(zhì)3相 關(guān) 課 程先修課程 離散數(shù)學(xué)（數(shù)理邏輯，集合論）

2、 計算機(jī)導(dǎo)論與程序設(shè)計、數(shù)據(jù)結(jié)構(gòu) 后續(xù)課程 編譯原理 其它相關(guān)課程模式識別、算法分析 4教材：形式語言與自動機(jī) 王柏 楊娟 編著 北京郵電大學(xué)出版社 2003.15 經(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） 清華大學(xué)出版社 （影印版） F

3、irst Edition 中譯本自動機(jī)理論、語言和計算導(dǎo)引 徐美瑞 等譯 科學(xué)出版社，1990 John.E.Hopcroft,the Turing Awardwinner in 1986.6 其它參 考 書 自動機(jī)理論及其應(yīng)用 何成武 科學(xué)出版社1990形式語言及其句法分析 美A.V. 阿霍 等 科學(xué)出版社1987 形式語言 王兵山，吳兵 編 國防工業(yè)大學(xué)出版社，1988 形式語言與自動機(jī) 陳有祺 編著 南開大學(xué)出版社，天津，1999 7為什么學(xué)習(xí)形式語言與自動機(jī)形式語言與自動機(jī)是計算機(jī)科學(xué)的基礎(chǔ)理論之一，是計算機(jī)學(xué)科的專業(yè)基礎(chǔ)課。在人工智能、電信領(lǐng)域等有廣泛的應(yīng)用。通過一些定理的證明和應(yīng)用

4、，對大家進(jìn)行思維訓(xùn)練，從而為今后學(xué)習(xí)通信軟件，協(xié)議工程，編譯技術(shù)，人工智能等內(nèi)容提供理論基礎(chǔ)。8對客觀世界的科學(xué)研究：目的在于把抽象數(shù)學(xué)的形式化體系發(fā)展成為與現(xiàn)實(shí)生活相似的理論模型，從而提供一種通用結(jié)構(gòu)來描述、理解和解決問題。計算機(jī)科學(xué)：是關(guān)于計算知識的有系統(tǒng)的整體。9計算機(jī)科學(xué)的兩個主要部分：構(gòu)成計算基礎(chǔ)的一些基本概念和模型；設(shè)計計算系統(tǒng)(軟件和硬件)的工程技術(shù)（設(shè)計理論的應(yīng)用）本課程著重介紹第一部分（涉及到一些第二部分的應(yīng)用），通過形式化技術(shù)對大家進(jìn)行思維訓(xùn)練，為今后的學(xué)習(xí)打好理論基礎(chǔ)。10形式語言與自動機(jī)概述及應(yīng)用本門課程將圍繞著什么是形式語言、什么是自動機(jī)、以及形式語言和自動機(jī)的相互關(guān)

5、系進(jìn)行闡述。核心內(nèi)容 有限狀態(tài)自動機(jī)，正規(guī)語言，正規(guī)表達(dá)式 上下文無關(guān)文法，上下文無關(guān)語言，下推 自動機(jī) 圖靈機(jī)，計算問題分類111形式語言什么是形式語言形式語言: 形式化描述的字母表上的字符串的集合。字母表：字符的有限集合。e.g.：26個英文字母構(gòu)成的字母表。字符串：字母表中的字符構(gòu)成的有限序列。e.g. hello, afjhkfyu 12為什么用形式語言自然語言：人們平時說話時所使用的一種語言，不同的國家和民族有著不同的語言。形式語言通過人們公認(rèn)的符號，表達(dá)方式所描述的一種語言，是一種通用語言，沒有國籍之分。形式語言是某個字母表上的字符串的集合，有一定的描述范圍。13例1： 漢語： 用

6、數(shù)字、符號等形式化的東西來描述語言我吃飯 語法正確我飯吃 語法錯誤飯吃我 語法正確，語義錯誤14例2：T為PASCAL語言所用的全部符號的集合。正確的PASCAL程序就是T上的語言。例3：在字母表T=a上，L = a 2n+1 | n =0 表示任意一對aa (包括0對) 后跟一個a的字符串。（即含有奇數(shù)個a的字符串。）15形式語言的最初起因： 語言學(xué)家（Chomsky）想用一套形式化方法來描述語言。形式語言在自然語言研究中起步，在計算機(jī)科學(xué)中得到廣泛應(yīng)用。最初的應(yīng)用：編譯 讓計算機(jī)按照語法規(guī)則將高級語言方便地翻譯成機(jī)器語言。16現(xiàn)在： 已廣泛應(yīng)用在人工智能、圖象處理、通信協(xié)議、通信軟件等多個

7、領(lǐng)域在計算機(jī)理論科學(xué)方面： 是可計算理論（算法在有限步驟內(nèi)求得解、算法復(fù)雜性、停機(jī)問題、）、定理自動證明、程序轉(zhuǎn)換（程序自動生成）、模式識別等的基礎(chǔ)。17比爾.蓋茨：人類計算的未來是讓計算機(jī)能夠看、聽、學(xué)，能用自然語言與人類交流 形式化非常重要18 2. 自動機(jī)什么是自動機(jī)？具有離散輸入輸出的數(shù)學(xué)模型。大量通信軟件的基本工作機(jī)制都是有限狀態(tài)自動機(jī)。自動機(jī)理論在通信領(lǐng)域中的應(yīng)用極為廣泛。19自動機(jī)接受一定的輸入，執(zhí)行一定的動作，產(chǎn)生一定的結(jié)果。使用狀態(tài)遷移描述整個工作過程。狀態(tài)：一個標(biāo)識，能區(qū)分自動機(jī)在不同時刻的狀況。有限狀態(tài)系統(tǒng)具有任意有限數(shù)目的內(nèi)部“狀態(tài)”自動機(jī)的本質(zhì)：根據(jù)狀態(tài)、輸入和規(guī)則決

8、定下一個狀態(tài)狀態(tài) 輸入（激勵） 規(guī)則 狀態(tài)遷移20為什么叫自動機(jī)？可能的狀態(tài)、運(yùn)行的規(guī)則都是事先確定的。一旦開始運(yùn)行，就按照事先確定的規(guī)則工作，因此叫“自動機(jī)”。有限自動機(jī)可以認(rèn)為是由一個帶有讀頭的有限控制器和一條寫有字符的輸入帶組成。21例1：打電話 (自動機(jī)在通信領(lǐng)域的應(yīng)用)。 在一次呼叫中，從建立連接到通話完畢，要經(jīng)歷摘機(jī)，撥號，應(yīng)答，進(jìn)行通話等過程，可以分別用四個狀態(tài)來表示。q0q1q2q3q4摘機(jī)收到撥號音撥號收應(yīng)答信號掛機(jī)收齊號碼q0:空閑狀態(tài)q1:等待撥號狀態(tài)q2:可以撥號狀態(tài)q3:等待應(yīng)答狀態(tài)q4:通話狀態(tài)22例2：串口通信 兩臺微機(jī)通過串口通信, 需在兩臺機(jī)器間建立好連接后，

9、才可以傳遞數(shù)據(jù)，可以使用有限狀態(tài)自動機(jī)，描述串口通信的狀態(tài)。傳輸數(shù)據(jù)收到應(yīng)答斷開連接連接請求q0q1q223根據(jù)結(jié)構(gòu)不同，自動機(jī)又可分為有限自動機(jī)，下推自動機(jī)，圖靈機(jī)等。下推自動機(jī)可以看作是由一條輸入帶，一個有限控制器和一個下推棧組成?；緢D靈機(jī)由一個具有讀寫頭的有限控制器和一條無限帶組成。使用自動機(jī)，可以形式化的描述現(xiàn)實(shí)世界中的一些問題。243形式語言與自動機(jī)的關(guān)系形式語言和自動機(jī)是密切相關(guān)的。形式語言 字符串自動機(jī) 字符串的識別系統(tǒng)根據(jù)復(fù)雜程度可將形式語言分類，根據(jù)自動機(jī)的接受能力、處理能力的不同也將自動機(jī)分類。二者之間具有較好的對應(yīng)關(guān)系。2526語言與有限自動機(jī)（Finite Autom

10、ata） 設(shè) = 0, 1 ， L = w w 中至少有一個0 ， 如 0011, 10, 110111 L, 而11, , 1111 L。下圖是一個可接受該語言的有限狀態(tài)自動機(jī)27小結(jié)文法是定義語言的一個數(shù)學(xué)模型，而自動機(jī)可看作是語言的識別系統(tǒng)。通過對一些定理的證明，說明對于一個文法產(chǎn)生的語言，可以構(gòu)造相應(yīng)自動機(jī)接受該語言：一個自動機(jī)接受的語言，可以構(gòu)造對應(yīng)的文法產(chǎn)生該語言。一定類型的自動機(jī)和某種類型的文法具有等價性。 28課程內(nèi)容及要求課程內(nèi)容： 書上二、三、四、五、六章。要求：通過本課學(xué)習(xí)，要求同學(xué)們掌握形式化描述方法，建立起形式語言與自動機(jī)的概念，并能在實(shí)際中加以應(yīng)用。通過對定理的證明

11、，對同學(xué)們進(jìn)行思維訓(xùn)練，并掌握一定的證明方法。29證 明 技 術(shù)* 基本證明方法 歸納證明技術(shù)* 引自清華大學(xué)計算機(jī)系軟件技術(shù)研究所王生原老師課件30演 繹 證 明 概念 一個 證明（proof）是命題的序列，其中的每一個命題或者是已知的命題，或者是由前面出現(xiàn)過的命題使用邏輯公理和規(guī)則得出. 已知的命題集合稱為假設(shè)（hypothesis）或前提（premise），最后一個命 題稱為該前提的結(jié)論（conclusion）. 31“If Then”命題 證明方法把 If 部分作為已知的命題，把 Then 部分作為結(jié)論. 舉例 如果x+y=1，那么x2-y2=x-y. 證明:1 x2-y2 = (x+

12、y)(x-y) / 數(shù)學(xué)公理2 (x+y) = 1 / 已知x2-y2 = x-y / 由1、2 和算術(shù)性質(zhì)推出32“If - And - Only - If ”命題 欲證 A if and only if B， 可分別證明如下兩個命題： 1 if A then B， 2 if B then A. 33有關(guān)集合的命題 設(shè) R, S 為集合. 欲證 R S， 可證明如下命題： if xR then xS 欲證 R = S， 可分別證明如下兩個命題： 1 if xR then xS 2 if xS then xR34原命題的逆否命題 有時，證明原命題的逆否(contrapositive) 命題更加

13、方便. 欲證 if A then B ， 可證明如下命題： if not B then not A35反證法 反證（proof by contradiction） 欲證 if H then C ，可以把 H 和 not C 都作為已知的命題，把任何一個矛盾( contradiction )命題作為新的結(jié)論.36舉例證明或否證 舉例證明存在量化的命題 如命題：存在整數(shù) a，滿足 a2 = 2a. 證明: 取 a = 2. ，滿足 a2 = 2a. 舉反例否定全稱量化的命題如命題：所有整數(shù) a，都滿足 a2=2a. 否證: 取 a = 1. ，不滿足 a2 = 2a. 37 集合的歸納定義 由 3

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

15、 ) ) 歸 納 定 義 與 結(jié) 構(gòu) 歸 納 法38 歸納定義合法括號串的集合 S 1 基礎(chǔ) 空串 S 2 歸納 若 xS ，則 (x) S ； 若 x,y S ，則 xy S . 3 極小性限制 S 中的元素只能由 1、2 生成 (或： S是滿足1、2的最小集合) 命題：合法括號串集合 S 中每個括號串的“(”與“)”數(shù)目相等 證明: 1 基礎(chǔ) 空串 的“(”與“)”數(shù)目相等，都為0； 2 歸納 設(shè) x,y 的“(”與“)”數(shù)目相等，前者為m ，后者為n ； (x) 的“(”與“)”數(shù)目都為m+1； xy 的“(”與“)”數(shù)目都為m+n. 歸納定義與結(jié)構(gòu)歸納證明（例）39 自然數(shù) 自然數(shù)集合

16、N是滿足如下條件的最小集合： (1) 0 N; (2) 若 n N, 則n的后繼n+1 N 數(shù)學(xué)歸納法 欲證對任意自然數(shù)n ，P(n)成立，(1) 先證 P(0) 成立; (2) 再證若 P(n)成立, 則P(n+1 )成立 另一種形式 (1) 先證P(0) 成立; (2) 再證若對任意kn， P(k) 成立, 則P(n)成立 對任何良序集合，都可以有這兩種形式基于自然數(shù)的歸納 一般數(shù)學(xué)歸納法40第二章 語言及文法主要內(nèi)容：定義形式語言的術(shù)語給出文法的定義和文法的分類要求掌握：語言和文法的形式定義CHOMSKY文法體系的分類。41第一節(jié) 語言的定義與運(yùn)算一、語言的一些術(shù)語： 字母表： 字符的有

17、限集合，記為T。 字符串： 由字母表T中的字符構(gòu)成的序列稱字母表T上的字符串（句子）。 常記為u,v,w,x,y,z； 常用a,b,c,d 標(biāo)識單個字符。42字 母 表 （Alphabet） 概念 形式符號的集合 記號 常用 T、 表示 舉例 英文字母表 a, b, , z, A, B , , Z 英文標(biāo)點(diǎn)符號表 , ; : . ? ! “ ” ( ) 漢字表 , 自, , 動 , , 機(jī), 化學(xué)元素表 H, He, Li, , T = a, n, y, 任,意 43字 符 串 （string） 概念 字母表 T 上的一個字符串（簡稱串），或稱為 字（word），為 T 中字符構(gòu)成的一個有限序

18、列。 空串（empty string）, 用 表示，不包含任何 字符。 舉例 設(shè) T = a, b ，則 , a, ba, bbaba 等都是串 字符串 w 的長度，記為 w ，是包含在 w 中字符的個數(shù) 舉例 = 0， bbaba = 5 ai 表示含有i個a的字符串44 連接（concatenation） 設(shè) x, y為串, 且 x a1a2 am, y b1b2 bn, 則 x 與 y 的連接 x y a1a2 am b1b2 bn 連接運(yùn)算的性質(zhì) ( x y ) z x（ y z ） x x x x y x+y 關(guān) 于 字 符 串 的 運(yùn) 算45 其它 如 取頭字符，取尾部，子串匹配

19、等 設(shè)1, 2, 3是字母表T上的字符串，稱1是字符串12的前綴，2是字符串12的后綴，且2是字符串123的子串。 空串是任何字符串的前綴，后綴及子串。 例：abc的前綴 a ab abc . 后綴 c bc abc . 子串 a b c ab bc abc , 即一個字符串可以看作是多個字符串的連接。 關(guān) 于 字 符 串 的 運(yùn) 算46 字符串的逆用 表示。 是字符串的倒置。= b1b2bn = bnbn-1b2b1 空串的逆還是47字 母 表 的 冪 運(yùn) 算 冪運(yùn)算 設(shè) T 為字母表，n 為任意自然數(shù)， 定義（1） T0 = （2）設(shè) x Tn-1，a T， 則a x Tn （3） Tn

20、中的元素只能由（1）和（2）生成 閉包 T* = T0 T1 T2 閉包 T+ = T1 T2 T3 T* = T+ ， T+ = T* 48閉包的物理意義 T的星號閉包T*：字母表T上的所有字符串和空串的集合。 T的正閉包T+：字母表T上的所有字符串構(gòu)成的集合。T*= T+ 舉例 設(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， 49語 言 （Languages） 概念 設(shè) T 為字母表，則任何集合 L T* 是字母表T上的一個語言（lang

21、uage） 舉例 英文單詞集 , English, , words , C 語言程序集 字母表？ 漢語成語集 , 馬到成功, 化學(xué)分子式集 , H2O, , NaCl , any, 任意 50語 言 （Languages）舉例：設(shè)T = a，b 則 L1 = anbn | n1 L3 = bk | k 是質(zhì)數(shù) L2 = 只有一個空句子的語言 L4 = = 空語言 均為字母表T上的語言。由語言的定義知語言是集合，對于集合的運(yùn)算可應(yīng)用于對于語言的計算。如并，交，補(bǔ)，差。51語言的基本運(yùn)算 語言的積：兩個語言L1 和L2的積L1 L2是由L1和L2中的字符串連接所構(gòu)成的字符串的集合。即L1中所有字符

22、串分別與L2中的字符串連接得到的集合。設(shè)T=a, b， L1和 L2是T上的語言。 L1 =ab, ba L2 =aa, bb則 L1 L2 =abaa, abbb, baaa, babb L2 L1 =aaab, aaba, bbab, bbba L1 L2 L2 L1 語言的積不可交換。52語言的基本運(yùn)算 語言的冪：語言的冪可歸納定義如下: L0 = Ln = L Ln-1 = Ln-1 L n 1上例中，L12 =abab, abba, baab, baba L22 =aaaa, aabb, bbaa, bbbb 53第二節(jié) 文法定義：所謂文法是用來定義語言的一個數(shù)學(xué)模型表示語言的方法：

23、若語言L是有限集合，可用列舉法若L是無限集合（集合中的每個元素有限長度），用其他方法。方法一：文法產(chǎn)生系統(tǒng)，由定義的文法規(guī)則產(chǎn)生出語言的每個句子方法二：機(jī)器識別系統(tǒng)：當(dāng)一個字符串能被一個語言的識別系統(tǒng)接受，則這個字符串是該語言的一個句子，否則不屬于該語言。54元語言定義：描述語言的語言例如：各種各樣的程序設(shè)計語言當(dāng)人們要解釋或討論程序設(shè)計語言本身時，又需要一種語言，被討論的語言叫做對象語言，即某種程序設(shè)計語言，討論對象語言的語言稱為元語言。55BNF（巴科斯范式） BNF范式通常被作為討論某種程序設(shè)計語言語法的元語言 := 0|1|2|9 := “定義為” := A|B|C|Z|a|b|z :

24、 = | | . 通過上述定義可知，所有以字母開頭的，由字母和數(shù)字組成的字符串都是標(biāo)識符。BNF定義了一種語言，其中標(biāo)識符如上定義。BNF描述它所定義的語言，為元語言。56例如：漢語語法中定義了句子的結(jié)構(gòu)由主語、謂語、賓語組成。這里主謂賓只是描述了句子的結(jié)構(gòu)，并不是句子。而按照這種結(jié)構(gòu)組成的建立在漢字上的字符串就是句子。如他是學(xué)生。文法是一種元語言，一種方法，根據(jù)文法產(chǎn)生出語言的句子。57三、Chomsky文法體系例如：BNF := := := :=a|b|z|A|B|Z :=0|1|9將:= 改為表示可被代替用I, L, D分別表示標(biāo)識符、字母、數(shù)字;58則上述表達(dá)式可以表示為 IL IIL

25、 IID La|b|.|z D0|1|.9這就是一個文法的生成式集合。59Chomsky文法體系中，任何一種文法必須包含有兩個不同的有限符號的集合，即非終結(jié)符集合N和終結(jié)符集合T。一個形式規(guī)則的有限集合P（生成式集合），一個起始符S。P中的生成式是用來產(chǎn)生語言句子的規(guī)則，而句子則是僅由終結(jié)符組成的字符串。這些字符串必須從一個起始符S開始，不斷使用P中的生成式而導(dǎo)出來?？梢娢姆ǖ暮诵氖巧墒降募?，它決定了語言中句子的產(chǎn)生。60文法的形式定義文法G是一個四元組G=(N，T，P，S)， 其中N 非終結(jié)符的有限集合T 終結(jié)符的有限集合 NT=P 形式為的生成式的有限集合。 且(NT)* N+ (NT

26、)* (NT)*S 起始符 且S N。61將上例用文法表示G=(N，T，P，S)N = I, L, DT = a, b, c,z, 0, 1, 9P = I, La, , D0, , D9S = I 文法是語言的產(chǎn)生系統(tǒng)，研究怎樣構(gòu)造文法能產(chǎn)生出符合要求的句子。62四推導(dǎo)與句型1、直接推導(dǎo)設(shè)G =（N,T,P,S）是文法，若A是P中的生成式，和是（NT）*中的字符串，則有A= 稱A直接推導(dǎo)出，或說是A的直接推導(dǎo)。63設(shè)G = (N,T,P,S)是文法，、0、1n、都是（NT）*中的字符串，且=0、 =n，其中i直接推導(dǎo)出i+1 （0in）,則稱序列0=1=2=n是長度為n的推導(dǎo)序列，而=0是長

27、度為0的推導(dǎo)序列。對推導(dǎo)出記為 ，若推導(dǎo)序列長度大于0，則記為 。推導(dǎo)序列的每一步，都產(chǎn)生一個字符串，這些字符串一般稱為句型。2、推導(dǎo)序列643、句型和句子句型字符串是文法G的句型，當(dāng)且僅當(dāng)S ，且（NT）*。 句子是G的句子，當(dāng)且僅當(dāng)S ,且T*。（是由終結(jié)符組成的字符串）例：I =L =a I =IL =LL =zL =zb句型包含句子654文法產(chǎn)生的語言由文法G產(chǎn)生的語言記為L(G)。 L(G) = |T*且S 或： L(G)中的一個字符串，必是由終結(jié)符組成的，并且是從起始符S推導(dǎo)出來的。66第三節(jié) Chomsky文法體系分類文法 G = (N,T,P,S)； P: 其中 （NT）* N+（NT）* （NT）* 屬于Chomsky文法體系該體系對生成式的形式做了一些規(guī)定，分為四類，即0型、1型、2型、3型文法0型文法：無限制文法對應(yīng)的語言：遞歸可枚舉語言，與圖靈機(jī)等價。671型文法也稱上下文有關(guān)文法（CSG：Context-sensitive Grammar)生成式的形式為，其中 |，（NT）+， （NT）*N+（NT）*對應(yīng)的語言：上下文有關(guān)語言（CSL：Context-sensitive Language)若不考慮，與線性有界自動機(jī)（LBA, Linear Bounded Automaton）等價。682型文法也稱上下文無關(guān)文法（CFG：Co