形式語(yǔ)言與自動(dòng)機(jī)：第01講-概論

1、形式語(yǔ)言與自動(dòng)機(jī)Formal Languages and Automata Theory課程定位：揭示計(jì)算機(jī)科學(xué)與技術(shù)學(xué)科中計(jì)算的本質(zhì)問(wèn)題 什么能且如何被（有效地）自動(dòng)計(jì)算。主要討論計(jì)算機(jī)理論與應(yīng)用中常用的各語(yǔ)言類對(duì)應(yīng)的計(jì)算模型以及模型之間的聯(lián)系與相互轉(zhuǎn)換。形式語(yǔ)言與自動(dòng)機(jī)課程目的： 培養(yǎng)計(jì)算機(jī)科學(xué)方面的理論素養(yǎng)，提高邏輯思維和解決相關(guān)問(wèn)題的能力，為今后從事科學(xué)研究或技術(shù)開發(fā)打下扎實(shí)的基礎(chǔ)。教材: 1、形式語(yǔ)言與自動(dòng)機(jī)理論（第二版），蔣宗禮等，清華出版社，2007參考教材： 2、形式語(yǔ)言與自動(dòng)機(jī)理論”，吳哲輝等編著，機(jī)械工業(yè)出版社，2008 “自動(dòng)機(jī)理論、語(yǔ)言和計(jì)算導(dǎo)論”，孫家嘯等譯，機(jī)械工業(yè)

2、出版社形式語(yǔ)言與自動(dòng)機(jī)前續(xù)課程： 離散數(shù)學(xué) 數(shù)理邏輯、集合論等MOOC素材: 1、自動(dòng)機(jī)(Automate），斯坦福大學(xué)CS154 /course/418/Automata/ 形式語(yǔ)言與自動(dòng)機(jī)形式文法與自動(dòng)機(jī)理論的發(fā)展概況學(xué)習(xí)意義與課程特點(diǎn)課程教學(xué)內(nèi)容與前期準(zhǔn)備符號(hào)語(yǔ)言第一章 課程概述及預(yù)備知識(shí)形式語(yǔ)言與自動(dòng)機(jī)理論的發(fā)展概況何為形式語(yǔ)言形式語(yǔ)言的研究概況計(jì)算模型相關(guān)研究領(lǐng)域何為“語(yǔ)言”：斯大林 語(yǔ)言是人們所理解的字和組合這些字的方法。韋波斯特 語(yǔ)言是為大范圍人群懂得、并能使用的字符以及組合這些字符的方法的一個(gè)統(tǒng)一體。形式語(yǔ)言語(yǔ)言：自然語(yǔ)言（ 英語(yǔ)、漢語(yǔ)）、 符號(hào)語(yǔ)言（ 程序設(shè)計(jì)語(yǔ)言、標(biāo)記語(yǔ)言、

3、算法 等）形式語(yǔ)言 元語(yǔ)言：用數(shù)學(xué)方法將符號(hào)語(yǔ)言抽象成一個(gè)數(shù)學(xué)系統(tǒng)，對(duì)其進(jìn)行嚴(yán)格的形式化定義，并構(gòu)建適當(dāng)?shù)拿枋瞿Ｐ停l(fā)展相關(guān)的知識(shí)和理論，使之在科學(xué)實(shí)踐中具有良好的指導(dǎo)作用。形式語(yǔ)言形式語(yǔ)言與自動(dòng)機(jī)理論的發(fā)展概況何為形式語(yǔ)言形式語(yǔ)言的研究概況計(jì)算模型相關(guān)研究領(lǐng)域 數(shù)理語(yǔ)言學(xué)家致力于用數(shù)學(xué)方法研究自然語(yǔ)言的結(jié)構(gòu)，試圖用計(jì)算機(jī)模擬。研究概況 1956年，賓夕法尼亞大學(xué)的語(yǔ)言學(xué)家 N. Chomsky 第一次提出用形式語(yǔ)言研究自然語(yǔ)言的方法。N. Chomsky 關(guān)于用形式文法派生語(yǔ)言的思路： 一組有限多個(gè)符號(hào)構(gòu)成的集合 ，稱為字母表 ； 中所有符號(hào)串構(gòu)成集合 *， * 每一個(gè)子集可視為上的一個(gè)語(yǔ)言

4、 L； 一個(gè)語(yǔ)言 L（所有句子） 可以按照文法 G L 的一系列描述規(guī)則（算法）形式化地派生出來(lái)。并給出了文法的喬姆斯基（Chomsky）體系。研究概況0 型文法（短語(yǔ)結(jié)構(gòu)文法或無(wú)限制文法）1 型文法（上下文有關(guān)文法）2 型文法（上下文無(wú)關(guān)文法） 3 型文法（正則文法）派生符號(hào)語(yǔ)言的喬姆斯基（Chomsky）文法體系：研究概況研究概況 1936年，英國(guó)數(shù)學(xué)家阿蘭.圖靈（A. M. Turing, 1912-1954）提出一種抽象計(jì)算模型 圖靈機(jī)( TM )，能根據(jù)內(nèi)部狀態(tài)，在一個(gè)無(wú)限長(zhǎng)磁帶上進(jìn)行讀、寫、移動(dòng)等簡(jiǎn)單操作，計(jì)算所有可計(jì)算的函數(shù)；是模擬計(jì)算機(jī)算法的計(jì)算邏輯和研究可計(jì)算性的形式化描述工

5、具。 TM 的兩個(gè)基本性質(zhì): 計(jì)算對(duì)象能用有窮方式描述; 計(jì)算過(guò)程必須由一系列離散的、可以機(jī)械執(zhí)行的步驟組成。識(shí)別符號(hào)語(yǔ)言的 A. Turing自動(dòng)機(jī)體系：基本的圖靈機(jī)模型的物理裝置：控制器：左右移動(dòng)、讀字符、修改方格字符、改變控制器狀態(tài) ； 模擬計(jì)算機(jī)的基本操作。裝置改進(jìn)：?jiǎn)螏Ф嗟?；子程序功能；單帶無(wú)窮；多帶；多維；通用 TM。研究概況研究概況1943年，McCulloch-Pitts神經(jīng)模型：莫克羅（WSMcCulloch）和彼特（WPitts）1951- 1956年，數(shù)學(xué)家克林（Kleene）：研究神經(jīng)細(xì)胞時(shí)，基于圖靈機(jī)建立了確定有窮狀態(tài)自動(dòng)機(jī) DFA，用其識(shí)別語(yǔ)言； 并證明DFA與RE

6、的等價(jià)性。 1957年，米凱爾.拉賓 & 達(dá)納.斯科特（Dana Stewart Scott，1976年圖靈獎(jiǎng)）將確定狀態(tài)自動(dòng)機(jī) DFA 擴(kuò)展為非確定有窮狀態(tài)自動(dòng)機(jī) NFA，從而簡(jiǎn)化了機(jī)器的描述建模過(guò)程，提高了解題（識(shí)別語(yǔ)言）速度，為其在機(jī)器翻譯、文獻(xiàn)檢索的語(yǔ)言識(shí)別及符號(hào)處理等中的應(yīng)用奠定了基礎(chǔ)。識(shí)別符號(hào)語(yǔ)言的 A. Turing 自動(dòng)機(jī)體系：?jiǎn)栴}：給定的形式文法和自動(dòng)機(jī)描述的是否是同一符號(hào)語(yǔ)言；兩種形式化方法是否等價(jià)；如何證明？二者能否在等價(jià)基礎(chǔ)上相互模擬與轉(zhuǎn)換？如何證明這種轉(zhuǎn)換的正確性？如何實(shí)現(xiàn)轉(zhuǎn)換的形式化和自動(dòng)化，即，是否能用計(jì)算機(jī)的算法實(shí)現(xiàn)？ 1959年，N.喬姆斯基發(fā)現(xiàn)：文法和自動(dòng)機(jī)

7、分別從派生和識(shí)別角度表達(dá)語(yǔ)言，并證明文法和自動(dòng)機(jī)的等價(jià)性，開啟了用數(shù)學(xué)方法研究形式語(yǔ)言的先河。研究概況0 型文法（無(wú)限制文法） 圖靈機(jī) 1 型文法（上下文有關(guān)文法） 線性有界自動(dòng)機(jī) 2 型文法（上下文無(wú)關(guān)文法） 下推自動(dòng)機(jī) 3 型文法（正則文法） 有窮狀態(tài)自動(dòng)機(jī) 兩種計(jì)算模型的對(duì)應(yīng)關(guān)系：研究概況1977 Amir Pnueli.將自動(dòng)機(jī)與邏輯建立關(guān)系，基于此發(fā)展了模型檢測(cè)技術(shù) * 判定性、復(fù)雜性、表達(dá)能力研究概況形式語(yǔ)言與自動(dòng)機(jī)理論的發(fā)展概況何為形式語(yǔ)言形式語(yǔ)言的研究概況計(jì)算模型相關(guān)研究領(lǐng)域計(jì)算模型相關(guān)研究領(lǐng)域1、可計(jì)算性問(wèn)題的提出：希爾伯特（D. Hilbert, 1862-1943）綱領(lǐng)

8、是否對(duì)各個(gè)數(shù)學(xué)分支都能建立一套形式化的公理系統(tǒng)，使得所涉及領(lǐng)域內(nèi)的任何命題，都可通過(guò)系統(tǒng)的有限步推導(dǎo)，判斷命題是否正確。2、存在不可判定命題：歌德?tīng)枺↘. Godel, 1906-1978） 在包含初等數(shù)論的協(xié)調(diào)的形式系統(tǒng)中，存在不可判定問(wèn)題；即，存在一個(gè)命題 A，無(wú)法在該系統(tǒng)內(nèi)證明 A 或 A 為真。3、可計(jì)算問(wèn)題轉(zhuǎn)換為： 是否存在這樣一種抽象的形式系統(tǒng)，它可以衡量什么問(wèn)題是可以判定（可計(jì)算）的，什么問(wèn)題是不可判定（不可計(jì)算）的。若干可計(jì)算模型：1、英國(guó)數(shù)學(xué)家圖靈 1936 年提出圖靈機(jī) 2、赫爾布拉德(1932)、哥德?tīng)枺?936）、克林尼（1936）提出一般遞歸函數(shù) 3、邱奇（1933-

9、1935 ）提出 - 演算 成果：1、邱奇證明：一般遞歸函數(shù) 同 - 可定義的等價(jià)性；2、克林尼證明：圖靈可計(jì)算 同 - 可定義的等價(jià)性；邱奇 - 圖靈論題：一個(gè)函數(shù)是可計(jì)算的當(dāng)且僅當(dāng)它是圖靈機(jī)可計(jì)算的（或 - 可定義的）。計(jì)算模型的相關(guān)研究領(lǐng)域形式文法與自動(dòng)機(jī)理論的發(fā)展概況學(xué)習(xí)意義與課程特點(diǎn)課程教學(xué)內(nèi)容與前期準(zhǔn)備符號(hào)語(yǔ)言第一章 課程概述及預(yù)備知識(shí)一、深化計(jì)算機(jī)基礎(chǔ)理論學(xué)習(xí)： 1、形式語(yǔ)言為計(jì)算機(jī)程序語(yǔ)言編譯過(guò)程提供了理論基礎(chǔ)； 3、有限狀態(tài)自動(dòng)機(jī)為數(shù)字邏輯電路等設(shè)計(jì)提供了描述手段； 2、圖靈機(jī)模型為計(jì)算機(jī)的計(jì)算理論提供了模型基礎(chǔ)。學(xué)習(xí)意義與課程特點(diǎn)三、人才培養(yǎng)： 形式語(yǔ)言與自動(dòng)機(jī)理論對(duì)于計(jì)算

10、機(jī)領(lǐng)域人才的計(jì)算思維能力的培養(yǎng)起到至關(guān)重要的作用。二、應(yīng)用拓展： 1、在人工智能的自然語(yǔ)言理解與翻譯、WEB服務(wù)標(biāo)注語(yǔ)言詞法及語(yǔ)法結(jié)構(gòu)與模式識(shí)別等方面有著廣泛的應(yīng)用。 2、為操作系統(tǒng)的狀態(tài)變換，網(wǎng)絡(luò)狀態(tài)描述等各種模型系統(tǒng)的建模提供方法。學(xué)習(xí)意義與課程特點(diǎn)“計(jì)算思維能力”梯級(jí)式訓(xùn)練過(guò)程：學(xué)習(xí)意義與課程特點(diǎn)本課程強(qiáng)調(diào)：1、抽象性：形式語(yǔ)言研究如何利用數(shù)學(xué)方法抽象出符號(hào)語(yǔ)言的結(jié)構(gòu)特征及相關(guān)的文法規(guī)則；自動(dòng)機(jī)理論研究各種能自動(dòng)處理符號(hào)串的計(jì)算模型；二者描述的理論基礎(chǔ)是離散數(shù)學(xué)，內(nèi)容具有一定抽象性。2、構(gòu)造性：課程包含大量的構(gòu)造性內(nèi)容，如給定語(yǔ)言構(gòu)造生成語(yǔ)言的形式文法或識(shí)別語(yǔ)言的自動(dòng)機(jī)；給定文法構(gòu)造等價(jià)

11、的自動(dòng)機(jī)等3、理論性：形式語(yǔ)言與自動(dòng)機(jī)理論的大部分內(nèi)容屬于理論形態(tài)，擁有完整的理論體系；包含許多定義、定理及其相關(guān)的遞歸證明。學(xué)習(xí)意義與課程特點(diǎn)形式文法與自動(dòng)機(jī)理論的發(fā)展概況學(xué)習(xí)意義與課程特點(diǎn)課程教學(xué)內(nèi)容與前期準(zhǔn)備符號(hào)語(yǔ)言第一章 課程概述及預(yù)備知識(shí)第四章 正則表達(dá)式以及其與文法、自動(dòng)機(jī)的等價(jià)性第三章 各種有限狀態(tài)自動(dòng)機(jī)及其相互等價(jià)性第五章 正則語(yǔ)言的性質(zhì)第六章 上下文無(wú)關(guān)文法第二章 形式文法28第一章 課程概述及預(yù)備知識(shí)課程教學(xué)內(nèi)容第七章 下推自動(dòng)機(jī)以及其與上下文無(wú)關(guān)文法的等價(jià)性第八章 圖靈機(jī)初步第九章 案例分析（語(yǔ)言驗(yàn)證、自然語(yǔ)言理解、狀態(tài)跟蹤等）課程前期準(zhǔn)備 集合與歸納證明集合的表示： 列

12、舉法、命題法集合的基數(shù)（勢(shì)）：有窮集合、可數(shù)無(wú)窮集合、不可數(shù)無(wú)窮集合集合關(guān)系的定義： A B 、 A = B、 集合的運(yùn)算： A B、A B、A B、A B、 A、(A ) = 2A、二元關(guān)系： 有序偶集合關(guān)系的性質(zhì)： 自反性、反自反性、對(duì)稱性、反對(duì)稱性、傳遞性等價(jià)關(guān)系： 具有自反、對(duì)稱、傳遞性質(zhì)的關(guān)系等價(jià)劃分與等價(jià)類： 用等價(jià)關(guān)系R對(duì)集合 S 進(jìn)行的劃分, 每個(gè)子集 Si 為一個(gè)等價(jià)類關(guān)系的合成與閉包： 正閉包，記為 “ R+ ” - 滿足 “傳遞” 性質(zhì)； 克林閉包，記為 “ R* ” - 滿足 “自反、傳遞” 性質(zhì)遞歸定義： 構(gòu)造無(wú)窮集合； 歸納證明： 證明無(wú)窮集合元素均具有 P 性質(zhì)形

13、式語(yǔ)言與自動(dòng)機(jī)理論的發(fā)展概況學(xué)習(xí)意義課程特點(diǎn)課程教學(xué)內(nèi)容與前期準(zhǔn)備符號(hào)語(yǔ)言第一章 課程概述及預(yù)備知識(shí)定義 1.1 字母表是一個(gè)非空有限集合，通常記作，其中元素稱為字母表的字符。字母表及其字符特點(diǎn)： 1、字母表具有非空、有窮性； 2、字符具有不可分性、整體性； 3、字符具有可區(qū)分性 、可辨認(rèn)性。字母表與字符串例：考察以下字母表： 1 = aa, ab, bb ； 2 = a, a, b, b ； 3 = a, b, a 。字母表與字符串定義 1.2 設(shè)1，2 是兩個(gè)字母表，1，2 的乘積定義為12 = ab | a 1 b 2 。例： 1、 0, 1 a, b, c = 0a, 0b, 0c,

14、1a, 1b, 1c ; 2、 a, b, c 0, 1 = a0, a1, b0, b1, 0c, c1 ; 3、 aa, ab, bb 0, 1 = aa0, aa1, ab0, ab1, bb0, bb1 字母表與字符串定義 1.3 設(shè)是一個(gè)字母表，的 n 次冪可遞歸定義為： 0 = ; n = n-1, n1， 其中，表示 由 0 個(gè)字符（空字符）組成。辨異 - 與 空集 的區(qū)別。定義 1.4 設(shè)是一個(gè)字母表， 的正閉包： + = 2 3 . , 的克林閉包： * = 0 2 3 . , 是 上全體字符串構(gòu)成的集合字母表與字符串例：1、 0, 1 + = 0, 1, 00, 01, 1

15、0, 11, 000, 001, 010, 011, 100, . ; 2、 0, 1 * = , 0, 1, 00, 01, 10, 11, 000, 001, 010, 011, 100, . ; 3、 a, b, c * = , a, b, c, aa, ab, ac, ba, bb, bc, , aaa, 字母表與字符串定義 1.5 設(shè)是一個(gè)字母表， x *， x 叫做 上的一個(gè)句子（字符串、符號(hào)串）。例： 1、 0, 1 * = , 0, 1, 00, 01, 10, 11, 000, 001, 010, 011, 100, . ; 2、 a, b, c * = , a, b, c,

16、 aa, ab, ac, ba, bb, bc, , aaa, 3、 an = aaa 表示 n 個(gè) a 組成的字符串。 例： | ab | = 2 , | aab | = 3, | an | = n , | a0 | = | = 0定義 1.6： 設(shè)是一個(gè)字母表， x *，字符串 x 中字符出現(xiàn)的總個(gè)數(shù)叫做該串的長(zhǎng)度，記作 | x |。字母表與字符串定義 1.7： 設(shè) 和 是任意兩個(gè)字符串，則 = 當(dāng)且僅當(dāng) | | = | |，并且組成 的字符與組成 的字符依次對(duì)應(yīng)相同。 例： 若 = ab， = ab， 則 = ； 若 = ab， = ba， 則 。 字母表與字符串定義 1.8 ： 1、設(shè)

17、 和 是 * 上任意的兩個(gè)字符串， 和 的連接構(gòu)成一個(gè)新句子，記作 （簡(jiǎn)記為 ），該句子由串 后直接接串 組成。字母表與字符串 2、對(duì)于 n 0，字符串 的 n 次冪為： （1） 0 = ；（2） n = n-1 例：設(shè) = 0, 1 , x = 001, y = 1101； 1、 x0 = y0 =; 2、 xy = 0011101; 3、x2 = 001001 4、 y4 = 1101110111011101,字符串連接性質(zhì)：對(duì)于* 上任意字符串 x, y, z, 連接運(yùn)算具有以下性質(zhì)： 1、結(jié)合律： ( xy ) z = x ( yz )。 2、左消去律： xy = xz y = z 。

18、 3、右消去律： yx = zx y = z 。 4、唯一性： 存在唯一確定的 a1, a2, , an , 使得 x = a1a2 an。 5、單位元素： = = 字母表與字符串 設(shè) 是一個(gè)字母表，任意字符串 x , y, z * ，且 x = yz， 則稱 y 是字符串 x 的前綴，z 是 x 的后綴；如果 z ，則稱 y 是 x 的真前綴；如果 y ，則稱 z 是 x 的真后綴。定義 1.9： 字母表與字符串例： 求 = a, b 上字符串 abaabb 的前綴、后綴、真前綴、真后綴？前綴： , a, ab, aba, abaa, abaab, abaabb真前綴： , a, ab, a

19、ba, abaa, abaab后綴： , b, bb, abb, aabb, baabb, abaabb真后綴： , b, bb, abb, aabb, baabb是每個(gè)字符串的前綴、后綴、子串。定義1.10： 設(shè)= a1 a2 an 是任意字符串，稱字符串 an a2 a1是的逆，記作T 若 = T，則稱為回文。字母表與字符串例：設(shè) = abcd， T = dcba例：字符串 0110110 和 deed 都是回文。定義 1.11： 設(shè)是任意字母表， L *， L 稱為字母表上的一個(gè)語(yǔ)言；x L， x 叫做 L 的一個(gè)句子。符號(hào)語(yǔ)言及其運(yùn)算性質(zhì)例：設(shè) = 0, 1 , 可定義 上的不同語(yǔ)言如

20、下： 1、 0, 1 ; 00, 11 ; 0, 1, 00, 11, 01, 10 ; 2、 0, 1 *; 00, 11 *; 0, 1, 00, 11, 01, 10 *; 定義 1.12 ：設(shè) 1 和 2 是字母表， L1 1*， L2 2*，L1 和 L2 的乘積 L1 L2= xy | x L1 y L2 是字母表 1 2 上的一個(gè)語(yǔ)言。例: 設(shè) L1 = ab，ac , L2 = e，bc , 有 L1L2 = abe，abbc， ace，acbc 。符號(hào)語(yǔ)言及其運(yùn)算性質(zhì)例：設(shè) = 0, 1 , 分析下列語(yǔ)言的結(jié)構(gòu)特征及其關(guān)系。1、有窮語(yǔ)言 ？無(wú)窮語(yǔ)言 ?2、L5L7 = L6

21、？ L5L7 = L8 ？ L9 = L10 ？3、 L6 L5L7 ？ L9 L10 ？ L6 L11？符號(hào)語(yǔ)言及其運(yùn)算性質(zhì)定理 1.1 ：設(shè) A、B、C、D 是 上任意語(yǔ)言，有 1）A = A = 2）A = A = A 3）（AB）C = A（BC）4）若 A B 和 C D，有 AC BD5）A（B C）= AB AC符號(hào)語(yǔ)言及其運(yùn)算性質(zhì) - 摘自離散數(shù)學(xué)書版本1P1456）（B C） A = B A C A7） A（B C） A B A C8）（B C）A B A C A9） Am An = Am+n10）（ Am ）n = Amn 11）若 A B，則 An Bn 符號(hào)語(yǔ)言及其運(yùn)算性質(zhì) 12）A* = A+ 13）An A*， 其中，n 0 14） An A+， 其中，n 1 15） A A B 16） A B A 17）若 A B，則 A B符號(hào)語(yǔ)言及其運(yùn)算性質(zhì)18）若 A B，則 A+ B+19） AA* = A*A =