形式語(yǔ)言與自動(dòng)機(jī)課件

1、形式語(yǔ)言與自動(dòng)機(jī)理論為什么學(xué)？學(xué)什么？怎么學(xué)？ 計(jì)算機(jī)科學(xué)與技術(shù)專(zhuān)業(yè)人員的4種基本專(zhuān)業(yè)能力：（1）計(jì)算思維能力；（2）算法的設(shè)計(jì)與分析能力；（3）程序設(shè)計(jì)和實(shí)現(xiàn)能力；（4）計(jì)算機(jī)軟硬件系統(tǒng)的認(rèn)知、分析、設(shè)計(jì)與應(yīng)用能力。引言 培養(yǎng)學(xué)生的形式化描述和抽象思維能力，了解和掌握 “問(wèn)題形式化描述自動(dòng)化（計(jì)算機(jī)化）” 的解題思路?！笆裁茨鼙挥行ё詣?dòng)化”計(jì)算學(xué)科之主題計(jì)算機(jī)科學(xué)與技術(shù)專(zhuān)業(yè)人員的4種基本專(zhuān)業(yè)能力：（1）計(jì)算思維能力；（2）算法的設(shè)計(jì)與分析能力；（3）程序設(shè)計(jì)和實(shí)現(xiàn)能力；（4）計(jì)算機(jī)軟硬件系統(tǒng)的認(rèn)知、分析、設(shè)計(jì)與應(yīng)用能力。引言 一、課程性質(zhì) Formal Languages and Autom

2、ata Theory The Fundamental of Computing Theory Introduction to the Theory of Computation二、課程特點(diǎn)： 抽象和形式化； 既有嚴(yán)格的理論證明； 又有很強(qiáng)的構(gòu)造性； 包含一些基本模型的建立、性質(zhì)等。三、課程主要內(nèi)容 1、語(yǔ)言理論 2、自動(dòng)機(jī)理論 3、可計(jì)算性基本理論本課程內(nèi)容屬于計(jì)算機(jī)科學(xué)的基本理論自然語(yǔ)言：人與人之間交流的基本手段。 如：漢語(yǔ)、英語(yǔ)、俄語(yǔ)、法語(yǔ)、等人工語(yǔ)言：主要用于人與計(jì)算機(jī)之間的交流。 如：程序設(shè)計(jì)語(yǔ)言 （也有例外，如世界語(yǔ)）語(yǔ)言理論： 語(yǔ)言自然語(yǔ)言人工語(yǔ)言形式語(yǔ)言：研究自然語(yǔ)言和人工語(yǔ)言都

3、必須遵循的一般規(guī)律 研究字符串集合及其性質(zhì)的學(xué)科Chomsky文法體系：4種類(lèi)型的文法及其產(chǎn)生的語(yǔ)言 正規(guī)文法RG正規(guī)語(yǔ)言RL； 上下文無(wú)關(guān)文法CFG上下文無(wú)關(guān)語(yǔ)言CFL； 上下文有關(guān)文法CSG上下文有關(guān)語(yǔ)言CSL； 無(wú)限制文法URG遞歸可枚舉語(yǔ)言r.e.。計(jì)算機(jī)處理的主要對(duì)象自動(dòng)機(jī)理論： 語(yǔ)言（形式語(yǔ)言）識(shí)別器 4種類(lèi)型自動(dòng)機(jī)與4類(lèi)文法相對(duì)應(yīng) 有限自動(dòng)機(jī)FA RL RG 下推自動(dòng)機(jī)PDA CFL CFG 線(xiàn)性界限自動(dòng)機(jī)LBACSL CSG 圖靈機(jī)TMr.e.URG 語(yǔ)言的運(yùn)算及性質(zhì)證明?？捎?jì)算性基本理論： 判定問(wèn)題與不可判定性形式語(yǔ)言（Formal Language）課程特點(diǎn)： 抽象和形式化

4、； 既有嚴(yán)格的理論證明； 又有很強(qiáng)的構(gòu)造性； 包含一些基本模型的建立、性質(zhì)等。四、教材與教學(xué)參考書(shū)教材：吳哲輝形式語(yǔ)言與自動(dòng)機(jī)理論，北京，機(jī)械工業(yè)出版社，2007年4月，20。主要參考書(shū)：J.Hopcroft,J.D.Ullman,Introduction to Automata Theory, Language and ComputationCalifornia, Addison-Wesley Publishing Company, 1979.（2002年清華，影印版） 2 劉田 譯，自動(dòng)機(jī)理論、語(yǔ)言和計(jì)算導(dǎo)論，機(jī)械工業(yè)出版社，2005， 39。 3蔣宗禮，形式語(yǔ)言與自動(dòng)機(jī)理論，清華大學(xué)出版

5、社，2003， 28。（另帶習(xí)題解答）另外的預(yù)備知識(shí) 1、關(guān)于集合及運(yùn)算（并、交、差、有限集、無(wú)限集、 冪集、笛卡爾乘積等） 2、關(guān)于二元關(guān)系（三歧性、等價(jià)關(guān)系、等價(jià)類(lèi)等） 3、關(guān)于常用證明方法（演繹推導(dǎo)、反證、例證、數(shù)學(xué)歸 納、構(gòu)造證明等） 4、樹(shù)和圖的應(yīng)用第1章 語(yǔ)言及其表示 語(yǔ)言某個(gè)字母表上滿(mǎn)足某些特定條件的字符串的集合1.1字母表、串和語(yǔ)言字母表（Alphabet）：由字符組成的非空有限集，通常用表示。 空 集 不能作為字母表 無(wú)限集 也不能作為字母表自然語(yǔ)言人工語(yǔ)言例如：英語(yǔ)的字母表=a, b, , y, z, A, B, Y,Z,，, 。, “，”,；=0,1也可以看作一個(gè)字母表，

6、一個(gè)二進(jìn)制數(shù)可看作這個(gè)字母表上的一個(gè)字符串。串（String）：由某字符表上的字符組成的有限序列。例如：0100101 是字母表=0,1上的一個(gè)串。串的長(zhǎng)度：一個(gè)串中字符的個(gè)數(shù)。 設(shè)x為字母表上的一個(gè)串，x的長(zhǎng)度記為|x|。例如 |0100101|=7空串：不含任何字符的串，即長(zhǎng)度為零的串，記為 。前綴、后綴、子串串的逆：把一個(gè)串中的字符逆向順序重新排列得到的另一個(gè)串 設(shè)x為一個(gè)串，x的逆記為xR 例： 若x=0100101 則xR=1010010 易知 1）|xR|=|x| 2）空串的逆仍是空串：R=串的連接（concatenation）運(yùn)算串的冪運(yùn)算 串的連接運(yùn)算又稱(chēng)為串的乘法運(yùn)算。類(lèi)似于

7、從數(shù)的乘法運(yùn)算推廣到數(shù)的冪運(yùn)算那樣，也可以從串的乘法推廣到串的冪運(yùn)算。 設(shè)x為一個(gè)串，則定義 代數(shù)系統(tǒng) 間的同構(gòu)關(guān)系語(yǔ)言（Language）語(yǔ)言幾種基本運(yùn)算對(duì)語(yǔ)言的理解句型、推導(dǎo)與句子文法所產(chǎn)生的語(yǔ)言舉例舉例1.3 語(yǔ)言識(shí)別器 語(yǔ)言識(shí)別器同文法一樣，都是對(duì)（可能為無(wú)限集的）語(yǔ)言提供有限表示的一種方式。語(yǔ)言識(shí)別器也稱(chēng)為自動(dòng)機(jī)。 如果說(shuō)文法是從產(chǎn)生語(yǔ)言的角度來(lái)表示語(yǔ)言，那么自動(dòng)機(jī)是從識(shí)別語(yǔ)言的角度來(lái)表示語(yǔ)言。 自動(dòng)機(jī)的結(jié)構(gòu)可以大致表示成下圖的形式。輔助存儲(chǔ)器a1a2an有限狀態(tài)控制器圖1.1 自動(dòng)機(jī)的大致結(jié)構(gòu)即自動(dòng)機(jī)由部分組成：有限狀態(tài)器、輸入帶和輔助存儲(chǔ)器。有的自動(dòng)機(jī)可以沒(méi)有輔助存儲(chǔ)器。 輸入帶

8、可以有限長(zhǎng)或無(wú)限長(zhǎng)，有限狀態(tài)控制器對(duì)輸入帶可以只允許讀，不允許寫(xiě)，也可以讀和寫(xiě)。 根據(jù)不同的規(guī)定，自動(dòng)機(jī)可以分為幾種類(lèi)型。第 2 章 正規(guī)表達(dá)式、正規(guī)文法與有限自動(dòng)機(jī) 正規(guī)語(yǔ)言是Chomsky文法體系中最簡(jiǎn)單的一類(lèi)語(yǔ)言。產(chǎn)生這種語(yǔ)言的文法是正規(guī)文法，識(shí)別這類(lèi)語(yǔ)言的是有限自動(dòng)機(jī)。此外，這類(lèi)語(yǔ)言也可以用正規(guī)表達(dá)式表示。因此，正規(guī)語(yǔ)言也叫正規(guī)集。 2.2 正規(guī)文法和正規(guī)語(yǔ)言 正規(guī)文法是Chomsky文法體系中最簡(jiǎn)單的一種文法。說(shuō)它簡(jiǎn)單，是指它的產(chǎn)生式的形式簡(jiǎn)單，因?yàn)楫a(chǎn)生式集是一個(gè)文法的核心。 定義和例子 2.3 有限自動(dòng)機(jī)（finite automaton,FA） 2.8 正規(guī)表達(dá)式和有限自動(dòng)機(jī)的應(yīng)

9、用 許多控制系統(tǒng)的控制部件都是時(shí)序電路。對(duì)于一個(gè)控制系統(tǒng)，可以把它的時(shí)序電路轉(zhuǎn)化為一個(gè)帶輸出的有限自動(dòng)機(jī)來(lái)分析系統(tǒng)的運(yùn)行。反過(guò)來(lái)，要設(shè)計(jì)一個(gè)復(fù)雜的控制系統(tǒng)，可以先設(shè)計(jì)出能夠?qū)崿F(xiàn)所要求得有限自動(dòng)機(jī)，然后把它轉(zhuǎn)化為時(shí)序電路。 本節(jié)主要討論兩個(gè)問(wèn)題：1）怎樣用一個(gè)有限自動(dòng)機(jī)描述一個(gè)時(shí)序電路？2）怎樣用一個(gè)時(shí)序電路來(lái)實(shí)現(xiàn)一個(gè)有限自動(dòng)機(jī)。用有限自動(dòng)機(jī)描述時(shí)序電路 我們對(duì)前面給出的時(shí)序電路的輪廓模型來(lái)加以說(shuō)明。由于x1, ，xn是一組輸入信號(hào)，所以有限自動(dòng)機(jī)的輸入字母表為 =0，1ny1, ,yk可以看作是系統(tǒng)的當(dāng)前狀態(tài)，加工后得到的w1,w2, ,wk，則是系統(tǒng)的下一狀態(tài)，從而系統(tǒng)的狀態(tài)集為 Q=0，1

10、kz1, ,z2是系統(tǒng)的輸出信號(hào)，所以輸出字母表為 =0，1m這樣，我們就得到一個(gè)帶輸出的有限自動(dòng)機(jī) 用時(shí)序電路實(shí)現(xiàn)有限自動(dòng)機(jī) 把M1中的狀態(tài)看作為k位邏輯值，輸入字符看作為n位邏輯值，輸出字母看作是m位邏輯值，這樣狀態(tài)轉(zhuǎn)換函數(shù)和輸出函數(shù)都可以用邏輯表達(dá)式表示，最后，就可以用邏輯電路（時(shí)序電路）來(lái)實(shí)現(xiàn)這些邏輯公式。 下面通過(guò)一個(gè)例子來(lái)說(shuō)明用時(shí)序電路實(shí)現(xiàn)帶輸出的有限自動(dòng)機(jī)的全過(guò)程。s1s2xu1u2t1t200000010011000010010001100111000000101101011001101111000第3章 上下文無(wú)關(guān)文法與下推自動(dòng)機(jī) 3.1 上下文無(wú)關(guān)文法（context-fr

11、ee grammer） 3.2 推導(dǎo)樹(shù)（derivation tree） 3.3 上下文無(wú)關(guān)文法的化簡(jiǎn) 3.4 喬姆斯基范式和格雷巴赫范式 3.5 上下文無(wú)關(guān)語(yǔ)言的固有歧義性第 4 章 圖靈機(jī) 4.2 圖靈機(jī)的基本概念 4.3 圖靈機(jī)用于計(jì)算整函數(shù) 4.5 變型圖靈機(jī) 除了定義4.1中給出的圖靈機(jī)的基本模型以外，圖靈機(jī)還可以有許多變型模型。這些模型的描述能力（接受語(yǔ)言的能力或計(jì)算函數(shù)的能力）同定義4.1的基本模型是等價(jià)的。下面列舉幾種：雙向無(wú)限帶圖靈機(jī) 這種圖靈機(jī)的讀寫(xiě)帶是向右、向左兩個(gè)方向無(wú)限延伸的。多帶圖靈機(jī) 這種圖靈機(jī)有多條讀寫(xiě)帶，每條讀寫(xiě)帶上都有讀寫(xiě)頭。在一個(gè)狀態(tài)下，圖靈機(jī)要把各條帶上

12、當(dāng)前格的信息都掃描到后，才能決定動(dòng)作函數(shù)的值。不確定的圖靈機(jī) 這種圖靈機(jī)在一個(gè)狀態(tài)下，掃描到一個(gè)字符，可以有多種動(dòng)作，其原理與NFA和NPDA類(lèi)似。脫線(xiàn)圖靈機(jī) 這種圖靈機(jī)專(zhuān)門(mén)用一條帶存放輸入串，不能在在這條帶上寫(xiě)。圖靈機(jī)另有工作帶，把輸入帶上的信息復(fù)制到工作帶后，在工作帶上可以讀和寫(xiě) 4.6 邱奇圖靈論題 自從歌德?tīng)柌煌耆远ɡ硖岢鲆院?，?jì)算科學(xué)家們認(rèn)識(shí)到存在不可計(jì)算的函數(shù)（不可判定的問(wèn)題）。那么，什么樣的函數(shù)是可計(jì)算的，哪些函數(shù)是不可計(jì)算的，有沒(méi)有一個(gè)鑒別標(biāo)準(zhǔn)呢？不久，圖靈、邱奇和克林尼克分別提出圖靈機(jī)、驗(yàn)算和遞歸函數(shù)等不同的計(jì)算模型。而且邱奇和圖靈都宣稱(chēng)他們提出的模型是可計(jì)算性的標(biāo)準(zhǔn)。由于

13、隨后證明了這三種模型的計(jì)算能力是等價(jià)的，因此，只要其中一種可以作為可計(jì)算性的衡量標(biāo)準(zhǔn)，另外兩種也就可以作為可計(jì)算性的衡量標(biāo)準(zhǔn)。因此，人們把邱奇和圖靈的斷言合稱(chēng)為邱奇圖靈論題。 之所以稱(chēng)為論題（hypohtesis），而不稱(chēng)為定理，是因?yàn)閷?duì)“可計(jì)算”這個(gè)術(shù)語(yǔ)無(wú)法給出形式定義，因此無(wú)法直接給出證明。書(shū)上通過(guò)證明可以用圖靈機(jī)模擬現(xiàn)代電子計(jì)算的極限模型隨機(jī)存取機(jī)（RAM）對(duì)邱奇圖靈論題給出有力的支持。 4.9 圖靈機(jī)帶符號(hào)的化簡(jiǎn) 在前面我們構(gòu)造圖靈機(jī)模型時(shí)，除了字母表中的字符以外，為了模擬方便，往往引入多個(gè)帶符號(hào)。其實(shí)，這種情況不是必須的。通過(guò)增加狀態(tài)的設(shè)置，可以把輸入字母以外的帶符號(hào)減少到只含一個(gè)空白符。4.10 圖靈機(jī)編碼與通用圖靈機(jī)4.10.1 圖靈機(jī)編碼 對(duì)于一個(gè)圖靈機(jī)，只要按順序列出它的全