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

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

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

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

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

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

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

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

9、用 許多控制系統的控制部件都是時序電路。對于一個控制系統，可以把它的時序電路轉化為一個帶輸出的有限自動機來分析系統的運行。反過來，要設計一個復雜的控制系統，可以先設計出能夠實現所要求得有限自動機，然后把它轉化為時序電路。 本節主要討論兩個問題：1）怎樣用一個有限自動機描述一個時序電路？2）怎樣用一個時序電路來實現一個有限自動機。用有限自動機描述時序電路 我們對前面給出的時序電路的輪廓模型來加以說明。由于x1, ，xn是一組輸入信號，所以有限自動機的輸入字母表為 =0，1ny1, ,yk可以看作是系統的當前狀態，加工后得到的w1,w2, ,wk，則是系統的下一狀態，從而系統的狀態集為 Q=0，1

10、kz1, ,z2是系統的輸出信號，所以輸出字母表為 =0，1m這樣，我們就得到一個帶輸出的有限自動機 用時序電路實現有限自動機 把M1中的狀態看作為k位邏輯值，輸入字符看作為n位邏輯值，輸出字母看作是m位邏輯值，這樣狀態轉換函數和輸出函數都可以用邏輯表達式表示，最后，就可以用邏輯電路（時序電路）來實現這些邏輯公式。 下面通過一個例子來說明用時序電路實現帶輸出的有限自動機的全過程。s1s2xu1u2t1t200000010011000010010001100111000000101101011001101111000第3章 上下文無關文法與下推自動機 3.1 上下文無關文法（context-fr

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

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

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