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

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

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

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

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

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

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

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

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

9、用 許多控制系統(tǒng)的控制部件都是時序電路。對于一個控制系統(tǒng)，可以把它的時序電路轉(zhuǎn)化為一個帶輸出的有限自動機(jī)來分析系統(tǒng)的運行。反過來，要設(shè)計一個復(fù)雜的控制系統(tǒng)，可以先設(shè)計出能夠?qū)崿F(xiàn)所要求得有限自動機(jī)，然后把它轉(zhuǎn)化為時序電路。 本節(jié)主要討論兩個問題：1）怎樣用一個有限自動機(jī)描述一個時序電路？2）怎樣用一個時序電路來實現(xiàn)一個有限自動機(jī)。用有限自動機(jī)描述時序電路 我們對前面給出的時序電路的輪廓模型來加以說明。由于x1, ，xn是一組輸入信號，所以有限自動機(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)的輸出信號，所以輸出字母表為 =0，1m這樣，我們就得到一個帶輸出的有限自動機(jī) 用時序電路實現(xiàn)有限自動機(jī) 把M1中的狀態(tài)看作為k位邏輯值，輸入字符看作為n位邏輯值，輸出字母看作是m位邏輯值，這樣狀態(tài)轉(zhuǎn)換函數(shù)和輸出函數(shù)都可以用邏輯表達(dá)式表示，最后，就可以用邏輯電路（時序電路）來實現(xiàn)這些邏輯公式。 下面通過一個例子來說明用時序電路實現(xiàn)帶輸出的有限自動機(jī)的全過程。s1s2xu1u2t1t200000010011000010010001100111000000101101011001101111000第3章 上下文無關(guān)文法與下推自動機(jī) 3.1 上下文無關(guān)文法（context-fr

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

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

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