形式語言與自動機-2015-第01講-概論

1、形式語言與自動機形式語言與自動機Formal Languages and Automata Theory教師：胡春明、趙永望、鄧婷教師：胡春明、趙永望、鄧婷課程定位：課程定位：揭示計算機科學(xué)與技術(shù)學(xué)科中計算的揭示計算機科學(xué)與技術(shù)學(xué)科中計算的本質(zhì)問題本質(zhì)問題 什么能且如何什么能且如何被（有效地）自動計算。被（有效地）自動計算。主要討論計算機理論與應(yīng)用中常用的各語言類對應(yīng)的主要討論計算機理論與應(yīng)用中常用的各語言類對應(yīng)的計算模型計算模型以及以及模型之間的聯(lián)系與相互轉(zhuǎn)換模型之間的聯(lián)系與相互轉(zhuǎn)換。形式語言與自動機形式語言與自動機課程目的：課程目的： 培養(yǎng)計算機科學(xué)方面的理論素養(yǎng)，提高邏輯思維和培養(yǎng)計算機

2、科學(xué)方面的理論素養(yǎng)，提高邏輯思維和解決相關(guān)問題的解決相關(guān)問題的能力，為今后從事科學(xué)研究或技術(shù)開發(fā)打下扎實的基礎(chǔ)。能力，為今后從事科學(xué)研究或技術(shù)開發(fā)打下扎實的基礎(chǔ)。教材教材: : 1 1、形式語言與自動機理論（第二版），蔣宗禮等，清華出版社，形式語言與自動機理論（第二版），蔣宗禮等，清華出版社，20072007參考教材：參考教材： 2、形式語言與自動機理論形式語言與自動機理論”，吳哲輝等編著，機械工業(yè)出版社，吳哲輝等編著，機械工業(yè)出版社，2008 “自動機理論、語言和計算導(dǎo)論自動機理論、語言和計算導(dǎo)論”，孫家嘯等譯，機械工業(yè)出版社，孫家嘯等譯，機械工業(yè)出版社形式語言與自動機形式語言與自動機前續(xù)課

3、程：前續(xù)課程： 離散數(shù)學(xué)離散數(shù)學(xué) 數(shù)理邏輯、集合論等數(shù)理邏輯、集合論等MOOCMOOC素材素材: : 1 1、自動機、自動機(Automate(Automate），斯坦福大學(xué)），斯坦福大學(xué)CS154CS154 http:/ 形式語言與自動機形式語言與自動機形式文法與自動機理論的發(fā)展概況形式文法與自動機理論的發(fā)展概況學(xué)習(xí)意義與課程特點學(xué)習(xí)意義與課程特點課程教學(xué)內(nèi)容與前期準(zhǔn)備課程教學(xué)內(nèi)容與前期準(zhǔn)備符號語言符號語言第一章第一章 課程概述及預(yù)備知識課程概述及預(yù)備知識形式語言與自動機理論的發(fā)展概況形式語言與自動機理論的發(fā)展概況何為形式語言何為形式語言形式語言的研究概況形式語言的研究概況計算模型相關(guān)研究領(lǐng)

4、域計算模型相關(guān)研究領(lǐng)域何為何為“語言語言”：斯大林斯大林 語言是人們所理解的字和組合這些字的方法。語言是人們所理解的字和組合這些字的方法。韋波斯特韋波斯特 語言是為大范圍人群懂得、并能使用的字符以語言是為大范圍人群懂得、并能使用的字符以及組合這些字符的方法的一個統(tǒng)一體。及組合這些字符的方法的一個統(tǒng)一體。形式語言形式語言語言：語言：自然語言（自然語言（ 英語、漢語）、英語、漢語）、 符號語言（符號語言（ 程序設(shè)計語言、標(biāo)記語言、算法程序設(shè)計語言、標(biāo)記語言、算法 等）等）形式語言形式語言 元語言：元語言：用數(shù)學(xué)方法將符號語言抽象成一個數(shù)學(xué)系統(tǒng)，對其進行嚴(yán)格用數(shù)學(xué)方法將符號語言抽象成一個數(shù)學(xué)系統(tǒng)，對

5、其進行嚴(yán)格的形式化定義，并構(gòu)建適當(dāng)?shù)拿枋瞿Ｐ?，發(fā)展相關(guān)的知識和的形式化定義，并構(gòu)建適當(dāng)?shù)拿枋瞿Ｐ?，發(fā)展相關(guān)的知識和理論，使之在科學(xué)實踐中具有良好的指導(dǎo)作用。理論，使之在科學(xué)實踐中具有良好的指導(dǎo)作用。形式語言形式語言形式語言與自動機理論的發(fā)展概況形式語言與自動機理論的發(fā)展概況何為形式語言何為形式語言形式語言的研究概況形式語言的研究概況計算模型相關(guān)研究領(lǐng)域計算模型相關(guān)研究領(lǐng)域 數(shù)理語言學(xué)家致力于用數(shù)學(xué)方法研究數(shù)理語言學(xué)家致力于用數(shù)學(xué)方法研究自然語言自然語言的結(jié)構(gòu)，試的結(jié)構(gòu)，試圖用計算機模擬。圖用計算機模擬。研究概況研究概況 1956年，賓夕法尼亞大學(xué)的語言學(xué)家年，賓夕法尼亞大學(xué)的語言學(xué)家 N. C

6、homsky 第一次第一次提出用形式語言研究自然語言的方法。提出用形式語言研究自然語言的方法。N. Chomsky 關(guān)于關(guān)于用形式文法派生語言的思路用形式文法派生語言的思路： 一組有限多個符號構(gòu)成的集合一組有限多個符號構(gòu)成的集合 ，稱為字母表，稱為字母表 ； 中所有符號串構(gòu)成集合中所有符號串構(gòu)成集合 *， * 每一個子集可視為每一個子集可視為上的一個語言上的一個語言 L； 一個語言一個語言 L（所有句子）（所有句子） 可以按照文法可以按照文法 G L 的一系列描的一系列描述規(guī)則（算法）形式化地派生出來。述規(guī)則（算法）形式化地派生出來。并給出了并給出了文法的喬姆斯基（文法的喬姆斯基（Chomsk

7、y）體系。）體系。研究概況研究概況0 型文法（短語結(jié)構(gòu)文法或無限制文法）型文法（短語結(jié)構(gòu)文法或無限制文法）1 型文法（上下文有關(guān)文法）型文法（上下文有關(guān)文法）2 型文法（上下文無關(guān)文法）型文法（上下文無關(guān)文法） 3 型文法（正則文法）型文法（正則文法）派生符號語言的喬姆斯基（派生符號語言的喬姆斯基（Chomsky）文法體系：）文法體系：研究概況研究概況研究概況研究概況 1936年，英國數(shù)學(xué)家阿蘭年，英國數(shù)學(xué)家阿蘭.圖靈圖靈（A. M. Turing, 1912-1954）提出提出一種抽象計算模型一種抽象計算模型 圖靈機圖靈機( TM )，能根據(jù)，能根據(jù)內(nèi)部狀態(tài)，在一個無限內(nèi)部狀態(tài)，在一個無限長

8、磁帶上進行讀、寫、移動等簡單操作，計算所有可計算的函數(shù)；長磁帶上進行讀、寫、移動等簡單操作，計算所有可計算的函數(shù)；是是模擬計算機算法的計算邏輯和研究可計算性的形式化描述工具。模擬計算機算法的計算邏輯和研究可計算性的形式化描述工具。 TM 的兩個基本性質(zhì)的兩個基本性質(zhì): 計算對象能用有窮方式描述計算對象能用有窮方式描述; 計算過程必須由一系列離散的、可以機械執(zhí)行的步驟組成。計算過程必須由一系列離散的、可以機械執(zhí)行的步驟組成。識別符號語言的識別符號語言的 A. Turing自動機體系：自動機體系：基本的圖靈機模型的物理裝置：基本的圖靈機模型的物理裝置：控制器：左右移動、讀字符、修改方格字符、改變控

9、制器狀態(tài)控制器：左右移動、讀字符、修改方格字符、改變控制器狀態(tài) ； 模擬計算機的基本操作。模擬計算機的基本操作。裝置改進：裝置改進：單帶多道；子程序功能；單帶無窮；多帶；多維；通用 TM。研究概況研究概況研究概況研究概況1943年，年，McCulloch-Pitts神經(jīng)模型：莫克羅神經(jīng)模型：莫克羅（WSMcCulloch）和彼特（）和彼特（WPitts）1951- 1956年，數(shù)學(xué)家克林（年，數(shù)學(xué)家克林（Kleene）：研究神經(jīng)細(xì)胞）：研究神經(jīng)細(xì)胞時，基于圖靈機建立了確定有窮狀態(tài)自動機時，基于圖靈機建立了確定有窮狀態(tài)自動機 DFA，用其，用其識別語言；識別語言； 并證明并證明DFA與與RE的等

10、價性。的等價性。 1957年，年，米凱爾米凱爾.拉賓拉賓 & 達(dá)納達(dá)納.斯科特斯科特（Dana Stewart Scott，1976年圖靈獎年圖靈獎）將確定狀態(tài)自動機）將確定狀態(tài)自動機 DFA 擴展為擴展為非確定有窮狀態(tài)自動機非確定有窮狀態(tài)自動機 NFA，從而，從而簡化了機器的描述建簡化了機器的描述建模過程，提高了解題（識別語言）速度，模過程，提高了解題（識別語言）速度，為其在機器翻為其在機器翻譯、文獻檢索的語言識別及符號處理等中的應(yīng)用奠定了譯、文獻檢索的語言識別及符號處理等中的應(yīng)用奠定了基礎(chǔ)?；A(chǔ)。識別符號語言的識別符號語言的 A. Turing 自動機體系：自動機體系：問題：問題：給定的給

11、定的形式文法形式文法和和自動機自動機描述的是否是同一符號語言；兩種形式化描述的是否是同一符號語言；兩種形式化方法是否等價；如何證明？二者能否在等價基礎(chǔ)上相互模擬與轉(zhuǎn)換？方法是否等價；如何證明？二者能否在等價基礎(chǔ)上相互模擬與轉(zhuǎn)換？如何證明這種轉(zhuǎn)換的正確性？如何實現(xiàn)轉(zhuǎn)換的形式化和自動化，即，如何證明這種轉(zhuǎn)換的正確性？如何實現(xiàn)轉(zhuǎn)換的形式化和自動化，即，是否能用計算機的算法實現(xiàn)？是否能用計算機的算法實現(xiàn)？ 1959年，年，N.喬姆斯基發(fā)現(xiàn)：文法和自動機分別從派生和識別角度喬姆斯基發(fā)現(xiàn)：文法和自動機分別從派生和識別角度表達(dá)語言，并證明文法和自動機的等價性，開啟了用數(shù)學(xué)方法研表達(dá)語言，并證明文法和自動機的

12、等價性，開啟了用數(shù)學(xué)方法研究形式語言的先河。究形式語言的先河。研究概況研究概況0 型文法（無限制文法）型文法（無限制文法） 圖靈機圖靈機 1 型文法（上下文有關(guān)文法）型文法（上下文有關(guān)文法） 線性有界自動機線性有界自動機 2 型文法（上下文無關(guān)文法）型文法（上下文無關(guān)文法） 下推自動機下推自動機 3 型文法（正則文法）型文法（正則文法） 有窮狀態(tài)自動機有窮狀態(tài)自動機 兩種計算模型的對應(yīng)關(guān)系：兩種計算模型的對應(yīng)關(guān)系：研究概況研究概況1977 Amir Pnueli.將自動機與邏輯建立關(guān)系，基于此發(fā)展將自動機與邏輯建立關(guān)系，基于此發(fā)展了模型檢測技術(shù)了模型檢測技術(shù) * 判定性、復(fù)雜性、表達(dá)能力判定性

13、、復(fù)雜性、表達(dá)能力研究概況研究概況形式語言與自動機理論的發(fā)展概況形式語言與自動機理論的發(fā)展概況何為形式語言何為形式語言形式語言的研究概況形式語言的研究概況計算模型相關(guān)研究領(lǐng)域計算模型相關(guān)研究領(lǐng)域計算模型相關(guān)研究領(lǐng)域計算模型相關(guān)研究領(lǐng)域1 1、可計算性問題的提出：、可計算性問題的提出：希爾伯特（希爾伯特（D. Hilbert, 1862-1943D. Hilbert, 1862-1943）綱領(lǐng)）綱領(lǐng) 是否對各個數(shù)學(xué)分支都能建立一套形式化的公理系統(tǒng)，使得所涉及領(lǐng)域是否對各個數(shù)學(xué)分支都能建立一套形式化的公理系統(tǒng)，使得所涉及領(lǐng)域內(nèi)的任何命題，都可通過系統(tǒng)的有限步推導(dǎo)，判斷命題是否正確。內(nèi)的任何命題，都

14、可通過系統(tǒng)的有限步推導(dǎo)，判斷命題是否正確。2 2、存在不可判定命題：、存在不可判定命題：歌德爾（歌德爾（K. Godel, 1906-1978K. Godel, 1906-1978） 在包含初等數(shù)論的協(xié)調(diào)的形式系統(tǒng)中，存在不可判定問題；即，存在包含初等數(shù)論的協(xié)調(diào)的形式系統(tǒng)中，存在不可判定問題；即，存在一個命題在一個命題 A A，無法在該系統(tǒng)內(nèi)證明，無法在該系統(tǒng)內(nèi)證明 A A 或或 A A 為真。為真。3 3、可計算問題轉(zhuǎn)換為：、可計算問題轉(zhuǎn)換為： 是否存在這樣一種抽象的形式系統(tǒng)，它可以衡量什么問題是可以判定是否存在這樣一種抽象的形式系統(tǒng)，它可以衡量什么問題是可以判定（可計算）的，什么問題是不可

15、判定（不可計算）的。（可計算）的，什么問題是不可判定（不可計算）的。若干可計算模型：若干可計算模型：1 1、英國數(shù)學(xué)家圖靈、英國數(shù)學(xué)家圖靈 1936 1936 年提出圖靈機年提出圖靈機 2 2、赫爾布拉德、赫爾布拉德(1932)(1932)、哥德爾（、哥德爾（19361936）、克林尼（）、克林尼（19361936）提出一般遞歸函數(shù)）提出一般遞歸函數(shù) 3 3、邱奇（、邱奇（1933-1935 1933-1935 ）提出）提出 - - 演算演算 成果：成果：1 1、邱奇證明：一般遞歸函數(shù)、邱奇證明：一般遞歸函數(shù) 同同 - - 可定義的等價性；可定義的等價性；2 2、克林尼證明：圖靈可計算、克林尼

16、證明：圖靈可計算 同同 - - 可定義的等價性；可定義的等價性；邱奇邱奇 - - 圖靈論題：圖靈論題：一個函數(shù)是可計算的當(dāng)且僅當(dāng)它是圖靈機可計算的一個函數(shù)是可計算的當(dāng)且僅當(dāng)它是圖靈機可計算的（或（或 - - 可定義的）。可定義的）。計算模型的相關(guān)研究領(lǐng)域計算模型的相關(guān)研究領(lǐng)域形式文法與自動機理論的發(fā)展概況形式文法與自動機理論的發(fā)展概況學(xué)習(xí)意義與課程特點學(xué)習(xí)意義與課程特點課程教學(xué)內(nèi)容與前期準(zhǔn)備課程教學(xué)內(nèi)容與前期準(zhǔn)備符號語言符號語言第一章第一章 課程概述及預(yù)備知識課程概述及預(yù)備知識一、深化計算機基礎(chǔ)理論學(xué)習(xí)：一、深化計算機基礎(chǔ)理論學(xué)習(xí)： 1、形式語言形式語言為計算機程序語言編譯過程提供了理論基礎(chǔ)；

17、 3、有限狀態(tài)自動機有限狀態(tài)自動機為數(shù)字邏輯電路等設(shè)計提供了描述手段； 2、圖靈機模型圖靈機模型為計算機的計算理論提供了模型基礎(chǔ)。學(xué)習(xí)意義學(xué)習(xí)意義與課程特點與課程特點三、人才培養(yǎng)：三、人才培養(yǎng)： 形式語言與自動機理論對于計算機領(lǐng)域人才的計算思維能力的培養(yǎng)起到至關(guān)重要的作用。二、應(yīng)用拓展：二、應(yīng)用拓展： 1、在人工智能的自然語言理解與翻譯、WEB服務(wù)標(biāo)注語言詞法及語法結(jié)構(gòu)與模式識別等方面有著廣泛的應(yīng)用。 2、為操作系統(tǒng)的狀態(tài)變換，網(wǎng)絡(luò)狀態(tài)描述等各種模型系統(tǒng)的建模提供方法。學(xué)習(xí)意義學(xué)習(xí)意義與課程特點與課程特點“計算思維能力計算思維能力”梯級式訓(xùn)練過程：梯級式訓(xùn)練過程：學(xué)習(xí)意義學(xué)習(xí)意義與課程特點與課

18、程特點本課程強調(diào)：本課程強調(diào)：1、抽象性：抽象性：形式語言研究如何利用數(shù)學(xué)方法抽象出符號語言的結(jié)構(gòu)特征及相關(guān)的文法規(guī)則；自動機理論研究各種能自動處理符號串的計算模型；二者描述的理論基礎(chǔ)是離散數(shù)學(xué)，內(nèi)容具有一定抽象性。2、構(gòu)造性：構(gòu)造性：課程包含大量的構(gòu)造性內(nèi)容，如給定語言構(gòu)造生成語言的形式文法或識別語言的自動機；給定文法構(gòu)造等價的自動機等3、理論性：理論性：形式語言與自動機理論的大部分內(nèi)容屬于理論形態(tài)，擁有完整的理論體系；包含許多定義、定理及其相關(guān)的遞歸證明。學(xué)習(xí)意義與學(xué)習(xí)意義與課程特點課程特點形式文法與自動機理論的發(fā)展概況形式文法與自動機理論的發(fā)展概況學(xué)習(xí)意義與課程特點學(xué)習(xí)意義與課程特點課程

19、教學(xué)內(nèi)容與前期準(zhǔn)備課程教學(xué)內(nèi)容與前期準(zhǔn)備符號語言符號語言第一章第一章 課程概述及預(yù)備知識課程概述及預(yù)備知識第四章第四章 正則表達(dá)式以及其與文法、自動機的等價性正則表達(dá)式以及其與文法、自動機的等價性第三章第三章 各種有限狀態(tài)自動機及其相互等價性各種有限狀態(tài)自動機及其相互等價性第五章第五章 正則語言的性質(zhì)正則語言的性質(zhì)第六章第六章 上下文無關(guān)文法上下文無關(guān)文法第二章第二章 形式文法形式文法28第一章第一章 課程概述及預(yù)備知識課程概述及預(yù)備知識課程教學(xué)內(nèi)容課程教學(xué)內(nèi)容第七章第七章 下推自動機下推自動機以及其與上下文無關(guān)文法的等價性以及其與上下文無關(guān)文法的等價性第八章第八章 圖靈機初步圖靈機初步第九章

20、第九章 案例分析（語言驗證、自然語言理解、案例分析（語言驗證、自然語言理解、狀態(tài)跟蹤等）狀態(tài)跟蹤等）課程前期準(zhǔn)備課程前期準(zhǔn)備 集合與歸納證明集合與歸納證明v集合的表示集合的表示： 列舉法、命題法列舉法、命題法v集合的基數(shù)（勢）集合的基數(shù)（勢）：有窮集合、可數(shù)無窮集合、不可數(shù)無窮集合有窮集合、可數(shù)無窮集合、不可數(shù)無窮集合v集合關(guān)系的定義集合關(guān)系的定義： A B 、 A = B、 v集合的運算集合的運算： A B、A B、A B、A B、 A、(A ) = 2A、v二元關(guān)系二元關(guān)系： 有序偶集合有序偶集合v關(guān)系的性質(zhì)關(guān)系的性質(zhì)： 自反性、反自反性、對稱性、反對稱性、傳遞性自反性、反自反性、對稱性、

21、反對稱性、傳遞性v等價關(guān)系等價關(guān)系： 具有自反、對稱、傳遞性質(zhì)的關(guān)系具有自反、對稱、傳遞性質(zhì)的關(guān)系v等價劃分與等價類等價劃分與等價類： 用等價關(guān)系用等價關(guān)系R對集合對集合 S 進行的劃分進行的劃分, 每個子集每個子集 Si 為一個等價類為一個等價類v關(guān)系的合成與閉包關(guān)系的合成與閉包： 正閉包，記為正閉包，記為 “ R+ ” - 滿足滿足 “傳遞傳遞” 性質(zhì)；性質(zhì)； 克林閉包，記為克林閉包，記為 “ R* ” - 滿足滿足 “自反、傳遞自反、傳遞” 性質(zhì)性質(zhì)v遞歸定義遞歸定義： 構(gòu)造無窮集合；構(gòu)造無窮集合； v歸納證明歸納證明： 證明無窮集合元素均具有證明無窮集合元素均具有 P 性質(zhì)性質(zhì)形式語言

22、與自動機理論的發(fā)展概況形式語言與自動機理論的發(fā)展概況學(xué)習(xí)意義課程特點學(xué)習(xí)意義課程特點課程教學(xué)內(nèi)容與前期準(zhǔn)備課程教學(xué)內(nèi)容與前期準(zhǔn)備符號語言符號語言第一章第一章 課程概述及預(yù)備知識課程概述及預(yù)備知識定義定義 1.1 字母表是一個字母表是一個非空有限非空有限集合，通常記作集合，通常記作，其中元素稱為，其中元素稱為字母表的字符。字母表的字符。字母表及其字符特點：字母表及其字符特點： 1 1、字母表具有非空、有窮性；字母表具有非空、有窮性； 2 2、字符具有不可分性、整體性；字符具有不可分性、整體性； 3 3、字符具有可區(qū)分性字符具有可區(qū)分性 、可辨認(rèn)性。、可辨認(rèn)性。字母表字母表與字符串與字符串例：考察

23、以下字母表：例：考察以下字母表： 1 = aa, ab, bb ； 2 = a, a, b, b ； 3 = a, b, a 。字母表字母表與字符串與字符串定義定義 1.2 設(shè)設(shè)1，2 是兩個字母表，是兩個字母表，1，2 的乘積定義為的乘積定義為12 = ab | a 1 b 2 。例：例： 1、 0, 1 a, b, c = 0a, 0b, 0c, 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 字母表字母表與字符串與字符串定義定

24、義 1.3 設(shè)設(shè)是一個字母表，是一個字母表，的的 n 次冪可遞歸定義為：次冪可遞歸定義為： 0 = ; n = n-1, n1， 其中，其中，表示表示 由由 0 個字符（空字符）組成。個字符（空字符）組成。辨異辨異 - 與與 空集空集 的區(qū)別。的區(qū)別。定義定義 1.4 設(shè)設(shè)是一個字母表，是一個字母表， 的正閉包：的正閉包： + = 2 3 . , 的克林閉包：的克林閉包： * = 0 2 3 . , 是是 上全體字符串構(gòu)成的集合上全體字符串構(gòu)成的集合字母表字母表與字符串與字符串例：例：1、 0, 1 + = 0, 1, 00, 01, 10, 11, 000, 001, 010, 011, 1

25、00, . ; 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è)設(shè)是一個字母表，是一個字母表， x *， x 叫做叫做 上的一個句子（上的一個句子（字符串、符號串）。字符串、符號串）。例：例： 1、 0, 1 * = , 0, 1, 00, 01, 10, 11, 000, 001, 010, 011, 100, . ; 2、 a, b, c * = ,

26、 a, b, c, aa, ab, ac, ba, bb, bc, , aaa, 3、 an = aaa 表示表示 n 個個 a 組成的字符串組成的字符串。 例：例： | ab | = 2 , | aab | = 3, | an | = n , | a0 | = | = 0定義定義 1.6： 設(shè)設(shè)是一個字母表，是一個字母表， x *，字符串字符串 x 中字符出現(xiàn)的總個中字符出現(xiàn)的總個數(shù)叫做該串的長度，記作數(shù)叫做該串的長度，記作 | x |。字母表與字母表與字符串字符串定義定義 1.7： 設(shè)設(shè) 和和 是任意兩個字符串，則是任意兩個字符串，則 = 當(dāng)且僅當(dāng)當(dāng)且僅當(dāng) | | = | |，并且組成并且

27、組成 的字符與組成的字符與組成 的字符依次對應(yīng)相同。的字符依次對應(yīng)相同。 例：例： 若若 = ab， = ab， 則則 = ； 若若 = ab， = ba， 則則 。 字母表與字母表與字符串字符串定義定義 1.8 ： 1、設(shè)、設(shè) 和和 是是 * 上任意的兩個字符串，上任意的兩個字符串， 和和 的連接構(gòu)成的連接構(gòu)成一個新句子，記作一個新句子，記作 （簡記為（簡記為 ），），該句子由串該句子由串 后直接后直接接串接串 組成。組成。字母表與字母表與字符串字符串 2、對于、對于 n 0，字符串，字符串 的的 n 次冪為：次冪為： （1） 0 = ；（；（2） n = n-1 例：設(shè)例：設(shè) = 0, 1

28、 , x = 001, y = 1101； 1、 x0 = y0 =; 2、 xy = 0011101; 3、x2 = 001001 4、 y4 = 1101110111011101,字符串連接性質(zhì)：字符串連接性質(zhì)：對于對于* 上任意字符串上任意字符串 x, y, z, 連接運算具有以下性質(zhì)：連接運算具有以下性質(zhì)： 1、結(jié)合律、結(jié)合律： ( xy ) z = x ( yz )。 2、左消去律：、左消去律： xy = xz y = z 。 3、右消去律：、右消去律： yx = zx y = z 。 4、唯一性：、唯一性： 存在唯一確定的存在唯一確定的 a1, a2, , an , 使得使得 x

29、= a1a2 an。 5、單位元素：、單位元素： = = 字母表與字母表與字符串字符串 設(shè)設(shè) 是一個字母表，任意字符串是一個字母表，任意字符串 x , y, z * ，且，且 x = yz， 則則稱稱 y 是字符串是字符串 x 的前綴，的前綴，z 是是 x 的后綴；如果的后綴；如果 z ，則稱，則稱 y 是是 x 的真前綴；如果的真前綴；如果 y ，則稱，則稱 z 是是 x 的真后綴。的真后綴。定義定義 1.9： 字母表與字母表與字符串字符串例：例： 求求 = a, b 上字符串上字符串 abaabb 的前綴、后綴、真前綴、真后綴？的前綴、后綴、真前綴、真后綴？前綴：前綴： , a, ab,

30、aba, abaa, abaab, abaabb真前綴：真前綴： , a, ab, aba, abaa, abaab后綴：后綴： , b, bb, abb, aabb, baabb, abaabb真后綴：真后綴： , b, bb, abb, aabb, baabb是每個字符串的前綴、后綴、子串。是每個字符串的前綴、后綴、子串。定義定義1.10： 設(shè)設(shè)= a1 a2 an 是任意字符串，稱字符串是任意字符串，稱字符串 an a2 a1是是的逆，的逆，記作記作T 若若 = T，則稱則稱為回文。為回文。字母表與字母表與字符串字符串例：設(shè)例：設(shè) = abcd， T = dcba例：字符串例：字符串 0

31、110110 和和 deed 都是回文。都是回文。定義定義 1.11： 設(shè)設(shè)是任意字母表，是任意字母表， L *， L 稱為字母表稱為字母表上的一個上的一個語言；語言； x L， x 叫做叫做 L 的一個句子。的一個句子。符號語言符號語言及其運算性質(zhì)及其運算性質(zhì)例：設(shè)例：設(shè) = 0, 1 , 可定義可定義 上的不同語言如下：上的不同語言如下： 1、 0, 1 ; 00, 11 ; 0, 1, 00, 11, 01, 10 ; 2、 0, 1 *; 00, 11 *; 0, 1, 00, 11, 01, 10 *; 定義定義 1.12 1.12 ：設(shè)設(shè) 1 和和 2 是字母表，是字母表， L1

32、1*， L2 2*，L1 和和 L2 的乘積的乘積 L1 L2= xy | x L1 y L2 是字母表是字母表 1 2 上的一個語言。上的一個語言。例例: 設(shè)設(shè) L1 = ab，ac , L2 = e，bc , 有有 L1L2 = abe，abbc， ace，acbc 。符號語言符號語言及其運算及其運算性質(zhì)性質(zhì)例：設(shè)例：設(shè) = 0, 1 , 分析下列語言的結(jié)構(gòu)特征及其關(guān)系。分析下列語言的結(jié)構(gòu)特征及其關(guān)系。1、有窮語言有窮語言 ？無窮語言？無窮語言 ?2、L5L7 = L6 ？ L5L7 = L8 ？ L9 = L10 ？3、 L6 L5L7 ？ L9 L10 ？ L6 L11？符號語言符號語

33、言及其運算及其運算性質(zhì)性質(zhì)定理定理 1.1 ：設(shè)：設(shè) A、B、C、D 是是 上任意語言，有上任意語言，有 1）A = A = 2）A = A = A 3）（AB）C = A（BC）4）若）若 A B 和和 C D，有有 AC BD5）A（B C）= AB AC符號語言及其符號語言及其運算運算性質(zhì)性質(zhì) - 摘自離散數(shù)學(xué)書版本1P145P1456）（）（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 符號語言及其符號語言及其運算運算性質(zhì)性質(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 符號語言及