形式語言配套全冊(cè)教學(xué)課件

《形式語言與自動(dòng)機(jī)理論》

第0章引言

0.1、課程緒論0.2、語言及其表示

0.3、文法

0.4、文法分類

0.5、識(shí)別程序----自動(dòng)機(jī)

0.6、課程內(nèi)容介紹0.1、課程緒論：

形式語言：大約于1956年問世，NoamChomsky給出了一種文法的數(shù)學(xué)模型，而后，用CFG文法描述ALGOL語言，最后導(dǎo)致了形式語言與自動(dòng)機(jī)理論的研究。形式語言---研究字符串集合及其性質(zhì)的學(xué)科計(jì)算機(jī)處理的主要對(duì)象語言自然語言(字符串)人工語言（符號(hào)串）自然語言：人與人之間交流的基本手段。如：漢語、英語、俄語、法語、…等人工語言：主要用于人與計(jì)算機(jī)之間的交流。如：程序設(shè)計(jì)語言（也有例外，如世界語）形式語言：研究自然語言和人工語言都必須遵循的一般規(guī)律自動(dòng)機(jī)：語言（形式語言）識(shí)別器可見，本課程是計(jì)算機(jī)科學(xué)的基本理論1、編譯理論的發(fā)展過程：匯編==〉編譯或解釋==〉CCCompiler(YACC)

上述過程中無不運(yùn)用某些形式語言的理論結(jié)果。2、形式語言的研究價(jià)值。（1）程序語言的設(shè)計(jì)（2）Compiler技術(shù)方法改進(jìn)（3）計(jì)算復(fù)雜性：算法與自動(dòng)機(jī)（4）NP問題（多項(xiàng)式時(shí)間復(fù)雜度問題）（4）人工智能技術(shù)發(fā)展：專家系統(tǒng)中知識(shí)表示（規(guī)則表示）及推理（規(guī)則推導(dǎo)）程序正確性證明，前置條件==〉結(jié)果分析軟件自動(dòng)生成，如CCCompiler、應(yīng)用軟件自動(dòng)構(gòu)造技術(shù)等自然語言理解，語言識(shí)別及分析技術(shù)3、形式語言與自動(dòng)機(jī)關(guān)系形式語言研究引入了自動(dòng)機(jī)進(jìn)行語言識(shí)別。自動(dòng)機(jī)就是一種自動(dòng)識(shí)別句子的構(gòu)造或程序。形式語言中的文法與自動(dòng)機(jī)之間存在不可分割的關(guān)系。每一種文法（四種典型文法）《=====》一種自動(dòng)機(jī)4、本課程只介紹一般的形式語言基本概念和理論“入門性”《參考書》1、《計(jì)算理論基礎(chǔ)》（第二版），HarryR.L.,ChristosH.P.，清華大學(xué)出版社，1999年9月2、《計(jì)算理論基礎(chǔ)》（第2版）中文翻譯版，張立昂、劉田譯，清華大學(xué)出版社，2000年7月3、《形式語言與自動(dòng)機(jī)理論》吳哲輝，吳振寰編著，機(jī)械工業(yè)出版社，2007年4月4、《形式語言與自動(dòng)機(jī)理論教學(xué)參考書》，蔣宗禮，清華大學(xué)出版社，2007年7月5、《形式語言及其與自動(dòng)機(jī)的關(guān)系》，[美]J.E.霍普克羅夫特，J.D.厄兒曼著；莫紹揆、段祥、顧秀芳譯，科學(xué)出版社出版，1979年6、《形式語言及其句法分析》，[美]A.V.阿霍，J.D.厄兒曼著，石青云譯科學(xué)出版社出版，1987年7、無論其它有關(guān)形式語言與自動(dòng)機(jī)理論的書。0.2、語言及其表示

提要：本節(jié)將從一般的觀點(diǎn)來討論定義語言的兩種主要方法：產(chǎn)生程序和識(shí)別程序。產(chǎn)生程序主要介紹Chomsky文法，而識(shí)別程序則介紹各種已研究過的識(shí)別程序。

1、過程和算法在討論有窮表示的概念以前，我們非形式地介紹一下過程和算法。一個(gè)過程就是一個(gè)能被機(jī)械地執(zhí)行的指令有窮系列。如一個(gè)計(jì)算機(jī)的程序?？偸且K止的過程叫做算法。2、語言的表示

語言定義：（非形式）一個(gè)語言L是在某個(gè)有限字母表∑上的有限長符號(hào)串的集合。1）羅列法：

當(dāng)L由有限符號(hào)串組成時(shí)，則一個(gè)顯然的表示法是把L中所有的符號(hào)串羅列出來。

L為無窮集時(shí)，怎么表示？假定要求（規(guī)定）語言的表示是有限的。2）產(chǎn)生系統(tǒng)：也稱為文法系統(tǒng)。

即可給予一種算法或過程，它依某種次序可系統(tǒng)地依次產(chǎn)生語言的句子。優(yōu)點(diǎn)：文法==〉句子結(jié)構(gòu)≡≡≡≡〉句法分析和翻譯簡單3）識(shí)別法：

給出一個(gè)過程，當(dāng)輸入一個(gè)任意的符號(hào)串時(shí)，它能判定該符號(hào)串（或句子）是否在語言中。實(shí)際上，我們必須要求該過程是一個(gè)算法。什么是語言理論？語言理論就是對(duì)符號(hào)行的集合、它們的表示法、結(jié)構(gòu)以及特性的研究。0.3、文法

1、啟示自然語言研究：文法的概念由語言學(xué)家在研究自然語言的過程中形式化了的。他們不但關(guān)心正確句子的識(shí)別，而且也關(guān)心提供句子的結(jié)構(gòu)性描述。目的：目標(biāo)之一是發(fā)展一種能夠描述自然語言(英語)的形式文法，從而解決自然語言的計(jì)算機(jī)化理解、翻譯和解決文字問題。但目前自然語言研究還不成熟，而計(jì)算機(jī)語言形式化已經(jīng)成熟。例1.1Thelittleboyranquickly。

<句子><名詞短語><動(dòng)詞短語><名詞短語><形容詞><形容詞><單名詞><單動(dòng)詞><副詞>ThelittleboyranQuickly.圖1、句子分析圖解句子分析分析上述句子的規(guī)則如下：<句子>→<名詞短語><動(dòng)詞短語><名詞短語>→<形容詞><名詞短語><名詞短語>→<形容詞><單個(gè)名詞><動(dòng)詞短語>→<單個(gè)動(dòng)詞><副詞><形容詞>→The<形容詞>→little<單個(gè)名詞>→boy<單個(gè)動(dòng)詞>→ran<副詞>→quickly注意：①目的：我們不但要能夠檢查句子的語法是否正確，而且還要能產(chǎn)生語法上正確的句子。②方法：從<句子>開始，利用規(guī)則到結(jié)束。這樣可以導(dǎo)出無窮多個(gè)句子中任何一個(gè)句子。③一般形式：{The,little}+╳{boyranquickly}

例如：littleTheTheboyranquickly.

這里，雖然大部分句子都沒有意義，然而在廣義上說還是語法上正確的句子。2、文法的形式概念

文法是語言的產(chǎn)生程序中最重要的一類，一個(gè)文法是定義語言的一個(gè)數(shù)學(xué)系統(tǒng)。這里，我們先考察一類文法，也稱為喬姆斯基文法或短語結(jié)構(gòu)文法。（0型文法）1）一個(gè)語言的文法需要用兩個(gè)不想交的符號(hào)集：終結(jié)符∑與非終結(jié)符N2）文法的核心是產(chǎn)生式規(guī)則集P：（N∪∑）*N（N∪∑）*╳（N∪∑）*3）文法定義：

約定：如果(α，β)是一個(gè)產(chǎn)生式，則用縮寫α→β來表示。定義：一個(gè)文法是一個(gè)四元組G=（N，∑，P，S），其中：（1）N是非終結(jié)符的有限集（變量集或句法種類集）。（2）∑是終結(jié)符的有限集，與N不相交。（3）P是（N∪∑）*N（N∪∑）*╳（N∪∑）*的有限子集，（α，β）∈P，可以寫成：α→β；稱為一個(gè)產(chǎn)生式。（4）S是N的一個(gè)特定符號(hào)，稱為句子符或起始符。例子1.2G1=（{A,S}，{0,1}，P，S）是一個(gè)文法，其中：P有下列產(chǎn)生式組成：

S→0A10A→00A1A→e

這里，非終結(jié)符是A和S；終結(jié)符是0和1。問題：1、該語言是什么樣？2、如何修改更簡單？

[討論]句子形式：一個(gè)文法按遞歸方式定義語言。遞歸地定義如下：（1）S是一個(gè)句子形式。（2）如果αβγ是一個(gè)句子形式，且β→δ是P中的產(chǎn)生式則αδγ也是一個(gè)句子形式。或，則α叫作句型。其中α∈（N∪∑）*句子：文法G的不含非終結(jié)符的一個(gè)句子形式稱由G生成的一個(gè)句子。語言：由文法G生成的語言記為L(G)，它是由G生成的所有句子的集合。即：

L(G)={w|w∈∑∧}S==>α*S==>w*G0.4、文法分類

按文法的產(chǎn)生式形式可以對(duì)文法進(jìn)行分類。喬姆斯基（Chomsky）文法分為四類：即0型、1型、2型、3型

[0型][1型][2型][3型]-------依次條件強(qiáng)硬

[0型文法]設(shè)G=（N,∑,P,S）為一文法，若其產(chǎn)生式均為如下結(jié)構(gòu)：

α→β其中:α（N×）*，且至少含有一個(gè)非終結(jié)符。

β（N×）*則稱此文法為0型文法?；蚍Q短語文法，或無(條件)限制文法。

如果對(duì)0型文法分別加上下列第i條限制，則就可得到相應(yīng)的i型文法：

1、若α→β∈P，則

，僅S→e例外（空句子）。

2、對(duì)于任何α→β∈P，則α=A∈N，β∈（N×）*

3、P中任何產(chǎn)生式均為A→αB，A→α；其中：α∈*，A,B∈N文法分類：0型文法：若α→β∈P，其中α,β（N×）*，稱為無限制文法，或稱短語文法。1型文法：若α→β∈P，則

，稱為上下文敏感的，或前后文有關(guān)文法。2型文法：若α→β∈P，則α=A∈N，β∈（N×）*，稱為上下文無關(guān)的，或前后文無關(guān)文法。3型文法：若P中產(chǎn)生式均為A→αB，A→α；其中：α∈*，A,B∈N；稱為右線性的，或正規(guī)文法。例子1.2是一個(gè)上下文有關(guān)的文法，即1型文法。(可改造成3型)例子1.3一個(gè)文法具有下列產(chǎn)生式規(guī)則：

S→0S|1S|e

此文法生成的語言是{0，1}*。該文法是一個(gè)右線性文法，即3型文法。約定：如果語言L能由x型的文法生成，就稱L是x型語言。比如：L(3)就由3型文法生成的語言，也就是3型語言。語言集合之關(guān)系：L(3)L(2)L(1)L(0)

0.5、識(shí)別程序----自動(dòng)機(jī)

自動(dòng)機(jī)與文法、語言的關(guān)系。對(duì)語言提供有限規(guī)定的另一種常用方法：對(duì)語言定義一個(gè)識(shí)別程序。也就是定義一個(gè)集合的高度格式化過程。1、識(shí)別程序的組成識(shí)別程序有三個(gè)部分：

a）一個(gè)輸入磁帶（字母表的線性序列）

b）一個(gè)有限狀態(tài)控制

c）一個(gè)輔助存儲(chǔ)（按某種結(jié)構(gòu)組織的存儲(chǔ)字母集合）a0a1a2a3……an…有限狀態(tài)控制輔助存儲(chǔ)輸入頭輸入磁帶圖示一個(gè)識(shí)別程序其中：輸入頭，一次可讀一個(gè)字母（方格）識(shí)別程序的一次移動(dòng)：左移一格、不動(dòng)、右移一格輔助存儲(chǔ)：可由兩個(gè)函數(shù)（即存函數(shù)和取函數(shù)）來刻畫其性能。例如：下推表。取函數(shù)f：

---為存儲(chǔ)字母表

f（Z1Z2…Zn）=Z1-----唯一能取最上端符號(hào)存函數(shù)：假定用一個(gè)有限長符號(hào)串代替下推表最上端的符號(hào)。

g：

*

*

g（Z1Z2…Zn,Y1…Yk）=Y1…YkZ2…Zn

輔助存儲(chǔ)的類型決定一個(gè)識(shí)別程序的名稱。如：以下推表為輔助存儲(chǔ)的識(shí)別程序稱為：下推識(shí)別程序（或叫下推自動(dòng)機(jī)）。識(shí)別程序的核心是一個(gè)有限狀態(tài)控制?？杀硎緸闋顟B(tài)的一個(gè)有限集，連同一個(gè)描述狀態(tài)如何隨當(dāng)前輸入符號(hào)（輸入頭處符號(hào)）和取自輔助存儲(chǔ)的當(dāng)前信息而改變的映射。同時(shí)，也決定輸入頭移動(dòng)及存儲(chǔ)什么信息。識(shí)別程序的運(yùn)算是作一系列移動(dòng)。移動(dòng)：①輸入頭向左移、向右移、保持不動(dòng)。②將信息存入輔助存儲(chǔ)。③改變控制的狀態(tài)。組態(tài)：一個(gè)識(shí)別程序的行為可由其組態(tài)來描述。

組態(tài)描述：①有限控制的狀態(tài)。②輸入磁帶的內(nèi)容，以及輸入頭的位置。③輔助存儲(chǔ)的內(nèi)容。

確定性的：在每一組態(tài)中最多存在一個(gè)可能的移動(dòng)。有限控制：

非確定性的：在每一組態(tài)，移動(dòng)不只一種，而屬于一個(gè)有限集。

①有限控制處于特定的初始狀態(tài)。初始組態(tài)：②輸入頭處在最左邊的符號(hào)。

③輔存中有特定的初始內(nèi)容。

①有限控制處于特定的最終狀態(tài)集中一個(gè)狀態(tài)。最終組態(tài)：②輸入頭處在右邊的結(jié)束標(biāo)記。

③輔助存儲(chǔ)也滿足一定的條件（最終）。接受符號(hào)串w：在輸入串w的條件下，能夠從初始組態(tài)開始作一系列移動(dòng)，（確定性）并結(jié)束于一個(gè)最終組態(tài)，則稱該識(shí)別程序接受輸入符號(hào)串w。接受符號(hào)串w：識(shí)別程序從初始組態(tài)開始，作許多不同的移動(dòng)序列。只要其中（非確定性）至少有一個(gè)序列結(jié)束于一個(gè)最終組態(tài)，則認(rèn)為符號(hào)串w被接受。例1.4設(shè)M是確定型有窮自動(dòng)機(jī)(K,

,,s,F

)，沒有存儲(chǔ)能力。其中： K=

{q0，q1}，

={a，b}，

s=

q0，

F={q0}，

是狀態(tài)轉(zhuǎn)移由右表給出的函數(shù)?？梢钥闯鯨(M)是有偶數(shù)個(gè)b的{a,b}*串。如果給Ｍ輸入aabba，則它的初始格局為(q0

，aabba)。于是

(q0，aabba)├M(q0，abba)

├M(q0，bba)

├M(q1，ba) ├M(q0，a)├M(q0，e)因此(q0

，aabba)├*M(q0，e),從而aabba被Ｍ接受。一般的，轉(zhuǎn)移函數(shù)可以表示成狀態(tài)圖形式，右上表對(duì)應(yīng)的狀態(tài)圖如右下。qσ(σ)q0aq0q0bq1q1aq1q1bq0aabbq0q1狀態(tài)圖語言：由一個(gè)識(shí)別程序定義的語言就是它所接受的輸入符號(hào)串的集合。Chomsky語言有下列特性：1、語言L是右線性的[3型]，當(dāng)且僅當(dāng)L由一個(gè)（單向確定性）有限自動(dòng)機(jī)所定義。2、語言L是上下文無關(guān)的[2型]，當(dāng)且僅當(dāng)L由一個(gè)（單向非確定性）下推自動(dòng)機(jī)所定義。3、語言L是上下文敏感的[1型]，當(dāng)且僅當(dāng)L由一個(gè)（雙向非確定性）線性有界自動(dòng)機(jī)所定義。4、語言L是遞歸可數(shù)的[0型]，當(dāng)且僅當(dāng)L由一個(gè)圖靈機(jī)所定義。最后，關(guān)于識(shí)別程序的精確定義可在我們課程教材中詳細(xì)討論。本課程主要教學(xué)內(nèi)容第一章集合、關(guān)系和語言第二章有窮自動(dòng)機(jī)。主要介紹“確定型有窮自動(dòng)機(jī)”、非確定型有窮自動(dòng)機(jī)及其與正則語言關(guān)系。討論了狀態(tài)最小化和有關(guān)算法。第三章上下文無關(guān)語言。介紹“下推自動(dòng)機(jī)”與上下文無關(guān)文法、語言；討論有關(guān)算法、確定性與語法分析等。第四章圖靈機(jī)（Turing）。介紹一般圖靈機(jī)，引入隨機(jī)存取圖靈機(jī)和非確定型圖靈機(jī)，討論了圖靈機(jī)計(jì)算、文法與數(shù)值函數(shù)。第五章不可判定性。討論停機(jī)問題、與圖靈機(jī)和文法有關(guān)的不可解問題、遞歸函數(shù)論等。第六章計(jì)算復(fù)雜性。介紹P類（多項(xiàng)式可判定的語言類）和NP類的復(fù)雜性問題，建立形式化數(shù)學(xué)理論來刻畫算法的實(shí)際可行性。第七章NP完全性。（相對(duì)獨(dú)立章）討論有關(guān)NP完全性問題。第1章集合、關(guān)系和語言

1.1、集合1.2、關(guān)系與函數(shù)1.3、特殊類型的二元關(guān)系

1.4、有窮集合與無窮集合1.5、三個(gè)基本的證明技術(shù)1.6、閉包與算法1.1、集合

集合：對(duì)象的匯集。

如：L={a,b,c,d}就是四個(gè)字母的匯集形成的集合。

元素或成員：構(gòu)成集合的所有對(duì)象。如：b是集合L的一個(gè)元素，表示成：b∈L

另一方面z不是L的元素，記作：zL

單元素集：集合中只有一個(gè)元素，即有一個(gè)元素構(gòu)成的集合。

空集：集合中沒有一個(gè)元素，用○表示。集合元素性質(zhì)定義：設(shè)集合A已經(jīng)定義，P是A的元素具有的性質(zhì)，則可以定義一個(gè)新集合B如下：

B={x:x∈A且x具有性質(zhì)P}

子集：如果集合A的每一個(gè)元素都是集合B的元素，則稱A是B的子集，記作：AB

真子集：如果AB，但A≠B，則稱A是B的真子集。集合的性質(zhì)：設(shè)A、B和C是集合，則下述算律成立1、冪等率A∪A=AA∩A=A2、交換律A∪B=B∪AA∩B=B∩A3、結(jié)合律(A∪B)∪C=A∪(B∪C)(A∩B)∩C=A∩(B∩C)4、分配律(A∪B)∩C=（A∩C)∪(B∩C)(A∩B)∪C=（A∪C)∩(B∪C)5、吸收律(A∪B)∩A=A(A∩B)∪A=A6、DeMorgan律A-(B∪C)=(A-B)∩(A-C)A-(B∩C)=(A-B)∪(A-C)冪集：集合A的所有子集的匯集本身是一個(gè)集合，叫做A的冪集記作：2A非空集合的劃分：如果∏是A的一些子集的集合，使得滿足

(1)∏的每一個(gè)元素非空，即非空集合；

(2)∏的不同元素是不相交的；

(3)∪∏=A，其中∪∏表示∏中所有元素的匯集

則∏是A的一個(gè)劃分。例如：{(a,b),{c},xmubah9}是{a,b,c,d}的一個(gè)劃分；奇自然數(shù)集合和偶自然數(shù)集合構(gòu)成自然數(shù)N的一個(gè)劃分。1.2、關(guān)系與函數(shù)

有序?qū)Γ河蓛蓚€(gè)元素構(gòu)成的對(duì)，前后有別。如a和b的有序?qū)τ涀?a,b)，a和b叫做它的分量。

迪卡兒積：兩個(gè)集合A和B的迪卡兒積是a∈A且b∈B的所有有序?qū)?a,b)構(gòu)成的集合，記作A×B。

二元關(guān)系：兩個(gè)集合A和B的二元關(guān)系是A×B的子集。

有序組：設(shè)n是任一自然數(shù)，如果a1,a2,…,an是任意n個(gè)對(duì)象，也可以有相同對(duì)象，則(a1,a2,…,an)是一個(gè)有序組。n叫做序列長度。從而就有：有序2元組、有序3元組、。。。有序n元組

n元關(guān)系：集合A1,…,An上的n元關(guān)系就是A1×。。。×An一個(gè)子集。即有序n元組的集合。

函數(shù)：集合A到集合B的函數(shù)是A和B上的具有下述特殊性質(zhì)的二元關(guān)系R:

對(duì)于每一個(gè)元素a∈A，在R中恰好存在一個(gè)有序?qū)σ詀為第一分量，第二分量b∈B。一般的，設(shè)f:A1×…×An|—B是一個(gè)函數(shù)，f(a1,…,an)=b，其中：

ai∈Ai，且b∈B，有時(shí)稱a1,…,an是f的自變量，b是f對(duì)應(yīng)的值。一對(duì)一：如果對(duì)任意兩個(gè)不同的值a,a’∈A，f(a)≠f(a’)

則稱函數(shù)f:A|—B是一對(duì)一的。滿射：如果B的每一個(gè)元素都是A的某一個(gè)元素在f下的值或叫象，則稱函數(shù)f:A|—B滿射到B。雙射：如果函數(shù)f:A|—B既是一對(duì)一的，又是滿射到B的，則稱f是A與B之間的雙射。二元關(guān)系R的逆：記作R-1，R-1={(a,b):(b,a)∈R}

顯然，若RA×B，則R-1

B×A。關(guān)系合成：設(shè)Q和R是兩個(gè)二元關(guān)系，他們的合成Q。R(簡記QR)為:QR={(a,b):對(duì)于某個(gè)c，(a,c)∈Q且(c,b)∈R}

注意：兩個(gè)函數(shù)f:A|—B和g:B|—C的合成是一個(gè)函數(shù)h:A|—C，使得對(duì)每一個(gè)a∈A，h(a)=g(f(a))1.3、特殊類型的二元關(guān)系

1、A×A的二元關(guān)系

設(shè)A是一個(gè)集合，RA×A是A上的一個(gè)二元關(guān)系，可以用一個(gè)有向圖表示關(guān)系R。

A的每一個(gè)元素用一個(gè)小圓圈表示(叫做有向圖的頂點(diǎn))，從a到b畫一個(gè)箭頭當(dāng)且僅當(dāng)(a,b)∈R，這些箭頭是該有向圖的邊。例如：用圖1-1中圖表示關(guān)系R={(a,b),(b,a),(a,d),(d,c),(c,c),(c,a)}adcb圖1-1二元關(guān)系的有向圖表示自反關(guān)系：如果對(duì)于每一個(gè)a∈A，(a,a)∈R，則稱關(guān)系RA×A是自反的對(duì)稱關(guān)系：如果只要(a,b)∈R就有(b,a)∈R，則稱關(guān)系RA×A是對(duì)稱的沒有(a,a)形式的有序?qū)Φ膶?duì)稱關(guān)系可以表示成無向圖或稱圖。反對(duì)稱關(guān)系：如果當(dāng)(a,b)∈R且a≠b時(shí)，(b,a)R，則稱關(guān)系R是反對(duì)稱的傳遞關(guān)系：如果只要(a,b)∈R且(b,c)∈R就有(a,c)∈R，則稱關(guān)系R是傳遞的等價(jià)關(guān)系：把自反、對(duì)稱、傳遞的關(guān)系叫做等價(jià)關(guān)系。如書上圖1-6。等價(jià)類：表示等價(jià)關(guān)系的無向圖由若干個(gè)集團(tuán)組成，把等價(jià)關(guān)系的這種集團(tuán)叫做等價(jià)類。定理1.3.1

設(shè)R是非空集合A上的等價(jià)關(guān)系，則R的等價(jià)類構(gòu)成A的一個(gè)劃分。（證明：利用等價(jià)關(guān)系性質(zhì)采用反證法，略）另外，由于二元關(guān)系R可以表示成圖，所以也有類似于圖的通路、長度、圈。1.4、有窮集合與無窮集合等勢：如果存在雙射函數(shù)f:A|—B，則稱集合A與B等勢。有窮集合：一般的，如果對(duì)某個(gè)自然數(shù)n，一個(gè)集合與{1,2,…,n}等勢，則稱這個(gè)集合是有窮的。無窮集合：如果一個(gè)集合不是有窮的，則稱它是無窮的。

例如：自然數(shù)集合N是無窮的；整數(shù)集合、實(shí)數(shù)集合都是無窮的?？蓴?shù)無窮的：稱與N等勢的集合是可數(shù)無窮的?？蓴?shù)的：稱有窮集合或可數(shù)無窮集合是可數(shù)的。（可枚舉的）相反，不是可數(shù)的集合稱為不可數(shù)的。另外，要證明集合A是可數(shù)無窮的，必須給出A與N之間的一個(gè)雙射函數(shù)f。見書1.5、三個(gè)基本的證明技術(shù)

1、數(shù)學(xué)歸納法的原理

如果A是一個(gè)自然數(shù)的集合使得：（1）0∈A；（2）對(duì)于每一個(gè)自然數(shù)n，{0,1,…,n}A蘊(yùn)函n+1∈A;

則A=N

非形式地說(數(shù)學(xué)歸納法的原理)：任何一個(gè)包含0的自然數(shù)集合，如果它具有下述性質(zhì)：它只要包含所有小于等于n的自然數(shù)就包含n+1，則它實(shí)際上就是全體自然數(shù)的集合。

一般的，用歸納法證明下述斷言：“對(duì)于所有的自然數(shù)n，性質(zhì)P成立?！庇孟率龇绞桨褦?shù)學(xué)歸納法原理應(yīng)用于集合A={n:對(duì)于n，P為真}：（1）基礎(chǔ)步驟：證明0∈A，即對(duì)于0，P成立。（2）歸納假設(shè)：假設(shè)對(duì)任意固定的n≥0，P對(duì)于0,1,…,n成立。（3）歸納步驟：利用歸納假設(shè)證明P對(duì)于n+1成立，于是根據(jù)歸納原理，A等于N，即P對(duì)于每一個(gè)自然數(shù)成立。2、鴿巢原理鴿巢原理：設(shè)A和B是兩個(gè)有窮集合，且|A|＞|B|，則不存在從A到B的一對(duì)一的函數(shù)。

換句話說，如果企圖把A的元素(“鴿子”)與B的元素(“鴿巢”)配對(duì)，遲早不得不把一只以上的鴿子放入一個(gè)巢里。鴿巢原理可以用第一個(gè)基本原理---數(shù)學(xué)歸納法證明。(見書上)定理1.5.1

設(shè)R是有窮集合A上的二元關(guān)系，a,b∈A。如果在R中有一條從a到b的通路，則有一條長度不超過|A|的通路。

證明：假設(shè)(a1,a2,…,an)是從a1=a到an=b的最短通路，即長度最小的通路，又假設(shè)n＞|A|。由鴿巢原理，A有一個(gè)元素重復(fù)出現(xiàn)在這條通路上，比如說ai=aj，1≤i＜j≤n。于是，(a1,a2,…,ai,aj+1,…,an)是另一條更短的從a到b的通路，這與假設(shè)(a1,a2,…,an)是從a到b的最短通路相矛盾。(完畢)3、對(duì)角化原理

對(duì)角化原理：設(shè)R是集合A上的二元關(guān)系，D={a:a∈A且(a,a)R}稱為R的對(duì)角線集合。對(duì)于每一個(gè)a∈A，令Ra={b:b∈A且(a,b)∈R}，則D與每一個(gè)Ra都不相同。

即，把R看成一個(gè)正方陣列，對(duì)角線的補(bǔ)與每一行都不同。（見書上例1.5.3）

理由：關(guān)于a是否是元素的問題，對(duì)角線集合D與Ra集合總是不同的。若a∈D，則必然(a,a)R；若a∈Ra，則必然(a,a)∈R;矛盾！即對(duì)角線上無關(guān)系的元素所在行自然不相等；對(duì)角線上有關(guān)系的元素又多余該對(duì)角線上元素。定理1.5.2

集合2N是不可數(shù)的。（自然數(shù)的冪集）證明：(大概思路)利用反證法假設(shè)它是可數(shù)無窮的，再利用對(duì)角線原理證明假設(shè)不成立。略，見書。1.6、閉包與算法

定義1.6.1

設(shè)RA2是集合A上的有向圖。R的自反傳遞閉包是關(guān)系

R*={(a,b):a,b∈A且在R中存在從a到b的通路}

例子見書圖1-9，構(gòu)造算法見P17下定義1.6.1函數(shù)的增長率：算法隨問題規(guī)模變化的增長規(guī)律。

(1)所有次數(shù)相同的多項(xiàng)式具有相同的增長率。

(2)nd≤2n

≤nn

例子：以R關(guān)系的自反傳遞閉包計(jì)算為例，說明函數(shù)增長率。

p17定義1.6.1算法復(fù)雜度O(nn+1)

p20改進(jìn)后新算法復(fù)雜度O(n5)

p21再改進(jìn)后新算法復(fù)雜度O(n3)

本科生算法分析和數(shù)據(jù)結(jié)構(gòu)課程中已經(jīng)介紹過。略。封閉性：

定義1.6.3

設(shè)D是一個(gè)集合，RDn+1是D上的一個(gè)n+1元關(guān)系，其中n≥0。又設(shè)B是D的子集。如果只要b1,…,bn∈B且(b1,…,bn,bn+1)∈R，就有bn+1∈B，則稱B在R下是封閉的。任何“集合B在關(guān)系R1,R2,…,Rm下是封閉的”形式的性質(zhì)稱為B的封閉性。定理1.6.1

設(shè)P是由集合D上的關(guān)系定義的封閉性，A是D的子集，則有唯一的包含A具有性質(zhì)P的極小集合B。（證明：略）閉包：定理1.6.1中的B是A在關(guān)系R1,…,Rm下的閉包。關(guān)于形式語言及表示我們前面已經(jīng)討論過。下面我們簡單地討論一下語言的有窮表示-----正則表達(dá)式與正則語言1.7語言的有窮表示-----正則表達(dá)式與正則語言

計(jì)算理論中一個(gè)核心問題：用有窮的規(guī)定說明表示無窮語言。例1.8.1令L={w∈{0,1}*：在w中1出現(xiàn)兩次或三次，并且第一次和第二次不相鄰}

這個(gè)語言可以只用單元集和語言運(yùn)算符號(hào)∪、。、*描述如下：

{0}*。{1}。{0}*。{0}

。{1}

。{0}*(({1}

。{0}*)∪⊙*)

進(jìn)一步簡單地寫成：

L=0*10*010*(10*∪⊙)---------正則表達(dá)式正則表達(dá)式定義：字母表上的正則表達(dá)式是字母表

∪{(,),⊙,∪,*}上可以如下獲得的所有字符串：

(1)、⊙和的每一個(gè)成員是正則表達(dá)式。

(2)、如果α和β是正則表達(dá)式，則(αβ)也是正則表達(dá)式。

(3)、如果α和β是正則表達(dá)式，則(α∪β)也是正則表達(dá)式。

(4)、如果α是正則表達(dá)式，則α*也是正則表達(dá)式。

(5)、除上述(1)-(4)得到之外，沒有任何別的正則表達(dá)式。

如果α是任意一個(gè)正則表達(dá)式，則L(α)是α表示的語言。即L是從字符串到語言的函數(shù)。函數(shù)L的定義：

(1)、L(⊙)=空集；對(duì)于每一個(gè)a∈，L(a)={a}(2)、如果α和β是正則表達(dá)式，則L((αβ))=L(α)L(β)(3)、如果α和β是正則表達(dá)式，則L((α∪β))=L(α)∪L(β)(4)、如果α是正則表達(dá)式，則L(α*)=L(α)*例1.8.2L(((a∪b)*a)是什么？計(jì)算如下：

L(((a∪b)*a)=L((a∪b)*)L(a)----由(2)得到

=L((a∪b)*){a}----由(1)得到

=L((a∪b))*{a}----由(4)得到

=(L(a)∪L(b))*{a}----由(3)得到

=({a}∪)*{a}----由(1)兩次得到

={a,b}*{a}={w∈{a,b}*：w以a結(jié)束}。例1.8.3(c*(a∪(bc*))*)表示的語言是什么？----該正則表達(dá)式表示{a,b,c}上不含子串a(chǎn)c的所有字符串的集合。正則語言：定義字母表∑上的正則語言類由所有可寫成L=L(α)的語言L組成，其中α是∑上的任一正則表達(dá)式。即，正則語言是所有能夠用正則表達(dá)式描述的語言。也就是，∑上的正則語言類恰好是語言集合{{a}：a∈∑}∪{⊙}關(guān)于并、連接和Kleene星號(hào)函數(shù)的閉包。語言識(shí)別裝置：專門為某個(gè)語言L設(shè)計(jì)的、用來回答“字符串w是L的成員嗎？”這樣的問題的算法。例如，識(shí)別語言L={w∈{0,1}*：w不含子串111}的裝置運(yùn)算如下：從左到右讀字符串，每次讀一個(gè)。有一個(gè)計(jì)數(shù)器，開始時(shí)為0，每當(dāng)在輸入串中遇到0時(shí)將它置回到0，每當(dāng)遇到1時(shí)加1。如果計(jì)數(shù)器已經(jīng)達(dá)到3，則停止計(jì)算并且回答“No”；如果讀完整個(gè)字符串且計(jì)數(shù)器沒有達(dá)到3，則停止計(jì)算并且回答“Yes”。

語言識(shí)別裝置和語言生成器是語言有窮說明的兩種類型。本課程后續(xù)將研究兩者之間的關(guān)系。（完）第二章有窮自動(dòng)機(jī)2.1確定型有窮自動(dòng)機(jī)2.2非確定型有窮自動(dòng)機(jī)2.3有窮自動(dòng)機(jī)與正則表達(dá)式2.4正則語言與非正則語言

2.5狀態(tài)最小化2.6關(guān)于有窮自動(dòng)機(jī)的算法一、有窮自動(dòng)機(jī)概念一個(gè)受到嚴(yán)格限制的實(shí)際計(jì)算機(jī)模型，有一個(gè)固定的、能力有限的“中心處理裝置”。它接收輸入，輸入是一個(gè)字符串并且被傳送到輸入帶上。沒有輸出，只給出是否接受這個(gè)輸入的信號(hào)。換句話說，它是一種語言識(shí)別裝置。有窮自動(dòng)機(jī)（FA）是具有離散輸入輸出系統(tǒng)的數(shù)學(xué)模型。這種系統(tǒng)內(nèi)部狀態(tài)數(shù)目是有限的。系統(tǒng)的狀態(tài)概括了對(duì)過去輸入處理狀況的信息。系統(tǒng)只需要根據(jù)當(dāng)前所處的狀態(tài)和面臨的輸入就可以決定系統(tǒng)的后繼行為。每當(dāng)系統(tǒng)處理了當(dāng)前的輸入后，系統(tǒng)的內(nèi)部狀態(tài)也將發(fā)生變化。使有窮自動(dòng)機(jī)成為這種受限制的模型的關(guān)鍵是：除固定的中心處理器之外它完全沒有存儲(chǔ)能力。2.1確定型有窮自動(dòng)機(jī)q0有窮控制器

q5q1.q4q2q3abababab輸入帶讀頭相關(guān)概念：輸入帶讀頭有限控制器狀態(tài)初始狀態(tài)終結(jié)狀態(tài)----------------接受語言與自動(dòng)機(jī)二.有窮自動(dòng)機(jī)的非形式描述

如果它從初始狀態(tài)開始，最后結(jié)束在一個(gè)終結(jié)狀態(tài)，則認(rèn)為輸入串被接受。

機(jī)器接受的語言是它接受的所有字符串的集合。圖2-1有窮自動(dòng)機(jī)二.確定型有窮自動(dòng)機(jī)定義2.1.1(形式定義)

一個(gè)確定型有窮自動(dòng)機(jī)是一個(gè)五元組M=(K,

,,s,F

). K是有窮狀態(tài)集

是字母表

s∈K是初始狀態(tài)

FK是終結(jié)狀態(tài)集合

是從K×到K的函數(shù)，叫做轉(zhuǎn)移函數(shù)。有窮自動(dòng)機(jī)M選取下一個(gè)狀態(tài)的規(guī)則被編碼成轉(zhuǎn)移函數(shù)。于是，如果M處于狀態(tài)q∈K且從輸入帶讀到的字符是a∈，則(q,a)∈K是M要轉(zhuǎn)移到的唯一確定的狀態(tài)。

確定型有窮自動(dòng)機(jī)(K,

,,s,F)的格局是K×*的任一元素。例如：上圖2－1表示的格局為（q2,ababab）二元關(guān)系├M在M的兩個(gè)格局之間成立當(dāng)且僅當(dāng)M能夠一步從一個(gè)格局變成另一個(gè)格局。于是，如果(q,ω)和(q’,ω’)是M的兩個(gè)格局，則(q,ω)├M(q’,ω’)當(dāng)且僅當(dāng)對(duì)于某個(gè)符號(hào)a∈Σ,ω=aω’且δ(q,a)=q’.這時(shí)我們稱(q,ω)一步產(chǎn)生

(q’,ω’)。用├*M表示├M的自反傳遞閉包。(q,ω)├*M(q’,ω’)讀作(q,ω)產(chǎn)生(q’,ω’)即在0步或若干步之后。稱字符串ω∈Σ*被M接受當(dāng)且僅當(dāng)存在q∈F使(s,ω)├*M(q,e)。M接受的語言是M接受的所有字符串的集合，記作L(M)。例2.1.1設(shè)M是確定型有窮自動(dòng)機(jī)(K,

,,s,F

)，其中

K=

{q0，q1}，

={a，b}，

s=

q0，

F={q0}，

是由右表給出的函數(shù)可以看出L(M)是有偶數(shù)個(gè)b的{a,b}*串。如果給Ｍ輸入aabba，則它的初始格局為(q0

，aabba)。于是

(q0，aabba)├M(q0，abba)

├M(q0，bba)

├M(q1，ba)

├M(q0，a)

├M(q0，e)因此(q0

，aabba)├*M(q0，e),從而aabba被Ｍ接受。一般的，轉(zhuǎn)移函數(shù)可以表示成狀態(tài)圖形式，右上表對(duì)應(yīng)的狀態(tài)圖如右下。對(duì)應(yīng)語言：(a*Uba*b)*qσ(σ)q0aq0q0bq1q1aq1q1bq0aabbq0q1狀態(tài)圖例2.1.2設(shè)計(jì)一臺(tái)接受語言L(M)＝{ω∈{a,b}*:ω不含有3個(gè)連續(xù)的b}的確定型有窮自動(dòng)機(jī)。令M=(K,

,,s,F

),其中 K={q0,q1,q2,q3},

={a,b}, s=q0, F={q0,q1,q2},由右表給出對(duì)應(yīng)的狀態(tài)圖如下：qσ(q,σ)q0aq0q0bq1q1aq0q1bq2q2aq0q2bq3q3aq3q3bq3q0q1q2q3aaaabbbb討論：習(xí)題2.1.2對(duì)應(yīng)語言：(a*∪(ba)*∪(bba)*)*(e∪b∪bb)2.2非確定型有窮自動(dòng)機(jī)

考慮語言L＝(ab∪aba)*,下圖給出的確定型有窮自動(dòng)機(jī)接受這個(gè)語言。

abbq0q1aaaabbbq3q2q4下圖的非確定型有窮自動(dòng)機(jī)也接受語言L＝(ab∪aba)*aabbq0q1q3aaebq0q1q3特點(diǎn)：1)非確定性指對(duì)于同一個(gè)輸入符號(hào)，允許幾個(gè)可能的“下一個(gè)狀態(tài)”

2)如左下圖，當(dāng)輸入為b時(shí)從q0出發(fā)不能進(jìn)入任何狀態(tài)。這是另一個(gè)特點(diǎn)。

3)在非確定型有窮自動(dòng)機(jī)狀態(tài)圖中允許標(biāo)記空串e的箭頭。如右圖也接受語言L。定義2.2.1

（形式定義）

一個(gè)非確定型有窮自動(dòng)機(jī)是一個(gè)五元組M=(K,

,Δ,s,F)，

其中

K是有窮狀態(tài)集合

是字母表

s∈K是初始狀態(tài)

FK是終結(jié)狀態(tài)集合

Δ

K×(∪{e})×K是轉(zhuǎn)移關(guān)系。

每一個(gè)三元組(q,u,p)∈Δ叫做M的一個(gè)轉(zhuǎn)移，它在形式定義中相當(dāng)于M的狀態(tài)圖中從q到p標(biāo)記u的箭頭。若M處于狀態(tài)q且下一個(gè)輸入符號(hào)為a，則M下次可以按照任意一個(gè)(q,a,p)或(q,e,p)形式的轉(zhuǎn)移進(jìn)行。若按(q,e,p)進(jìn)行，則不讀入任何符號(hào)。非確定有窮自動(dòng)機(jī)計(jì)算的形式定義與確定性自動(dòng)機(jī)很類似，包括：

格局(K×*的元素)、一步產(chǎn)生(├M)及其若干步產(chǎn)生(├*M)接受ω：字符串ω∈Σ*被M接受當(dāng)且僅當(dāng)存在狀態(tài)q∈F使得

(s,ω)├*M(q,e)定義語言：M接受的語言L(M)是所有M接受的字符串的集合。例2.2.1下圖描述一臺(tái)非確定型有窮自動(dòng)機(jī)，接受含有模式bb或者bab出現(xiàn)的所有字符串的集合。形式地，這臺(tái)機(jī)器是(K,

,Δ,s,F)其中:K={q0,q1,q2,q3,q4}

={a,b} s=q0

F={q4}

以及Δ={(q0,a,q0),(q0,b,q0),(q0,b,q1), (q1,b,q2),(q1,a,q3),(q2,e,q4), (q3,b,q4),(q4,a,q4),(q4,b,q4)}

當(dāng)給M輸入字符串bababab時(shí)，可能產(chǎn)生幾個(gè)不同的動(dòng)作序列。例如，只使用(q0,a,q0)和(q0,b,q0)，M結(jié)束在非終結(jié)狀態(tài)q0。見P41中

但使用規(guī)則3、5、7、8、9，多種使M結(jié)束在終結(jié)狀態(tài)q4。見P41下注意：一個(gè)字符串被非確定型有窮自動(dòng)機(jī)接受當(dāng)且僅當(dāng)至少有一個(gè)引導(dǎo)到終結(jié)狀態(tài)的計(jì)算序列，所以bababab∈L(M)。a,baebq0a,bbbq2q1q3q4定理2.2.1

對(duì)于每一臺(tái)非確定型有窮自動(dòng)機(jī)，有一臺(tái)等價(jià)的確定型有窮自動(dòng)機(jī)。(注：構(gòu)造性證明)

關(guān)鍵思想：認(rèn)為非確定有窮自動(dòng)機(jī)在任一時(shí)刻不是處于一個(gè)狀態(tài)，而是處于一個(gè)狀態(tài)集合，即從初始狀態(tài)出發(fā)通過消耗相同的輸入能夠到達(dá)的所有狀態(tài)。

e動(dòng)作集：對(duì)任一狀態(tài)q∈K，令E(q)等于M從狀態(tài)q開始、不讀任何輸入能夠到達(dá)的所有狀態(tài)的集合。

E（q）={p∈K:(q,e)├*M（p，e）}

形式化定義：設(shè)有一臺(tái)非確定性有窮自動(dòng)機(jī)M=(K,

,Δ,s,F)

，與之等價(jià)的確定性有窮自動(dòng)機(jī)M’=(K’,

,’,s’,F’

)，其中：

K’=2ks’=E(s)F’={Q:QK∧Q∩F≠⊙}

’(Q,a)=∪{E(p):p∈K且對(duì)某個(gè)q∈Q,(q,a,p)∈△}

即取’(Q,a)

為M從Q中的狀態(tài)出發(fā)通過讀輸入符號(hào)a可以到達(dá)的所有狀態(tài)的∪{E(p)集合。斷言：對(duì)于任一字符串ω∈Σ*和任意狀態(tài)p,q∈K，(q,ω)├*M(p,e)

當(dāng)且僅當(dāng)對(duì)于某個(gè)包含p的集合P,(E(q),ω)├*M’

(P,e)定理證明：證明M’是確定性的和等價(jià)于M。1）證明M’是確定性的，只要注意到’是單值函數(shù)，并且對(duì)所有的Q∈K’和a∈Σ都有定義。2）證明M與M’等價(jià)，考慮任一字符串ω∈Σ*

。于是，ω∈L(M)當(dāng)且僅當(dāng)對(duì)于某個(gè)f∈F，(s,ω)├*M(f,e)---跟據(jù)L(M)定義當(dāng)且僅當(dāng)對(duì)于某個(gè)包含f的Q，(E(s),ω)├*M’(Q,e)---跟據(jù)斷言當(dāng)且僅當(dāng)對(duì)于某個(gè)Q∈F’,(s’,ω)├*M’(Q,e)---跟據(jù)L(M’)定義當(dāng)且僅當(dāng)ω∈L(M’)3)斷言證明，對(duì)|ω|做歸納，證明上述斷言。（見書，略）aaeq0q1aeebebq3q2q4例2.2.3右圖是一臺(tái)非確定性有窮自動(dòng)機(jī)。e動(dòng)作集如下：E(q0)={q0,q1,q2,q3}E(q1)={q1,q2,q3}E(q2)={q2}E(q3)={q3}E(q4)={q3,q4}構(gòu)造相應(yīng)的確定性有窮自動(dòng)機(jī)如下：s’=E(q0)={q0,q1,q2,q3}由于s’中狀態(tài)存在(q1,a,q0)、(q1,a,q4)、(q3,a,q4)故：’(s’,a)=E(q0)∪E(q4)={q0,q1,q2,q3,q4}同理，’(s’,b)=E(q2)∪E(q4)={q2,q3,q4}’({q0,q1,q2,q3,q4},a)=E(q0)∪E(q4)={q0,q1,q2,q3,q4}’({q0,q1,q2,q3,q4},b)=E(q2)∪E(q4)={q2,q3,q4}’({q2,q3,q4},a)=E(q4)={q3,q4}’({q2,q3,q4},b)=E(q4)={q3,q4}’({q3,q4},a)=E(q4)={q3,q4}’({q3,q4},b)=⊙另外，’(⊙,a)=’(⊙,b)=⊙故構(gòu)造出的確定性有窮自動(dòng)機(jī)如右下圖所示。（討論習(xí)題2.2.1）abbaaaabb{q0,q1,q2,q3,q4}{q0,q1,q2,q3}{q2,q3,q4}{q3,q4}⊙b2.3有窮自動(dòng)機(jī)與正則表達(dá)式本節(jié)內(nèi)容：證明有窮自動(dòng)機(jī)（確定的和非確定的）接收的語言類與正則表達(dá)式描述的語言類（正則語言類）相同。

正則語言類：某些有窮的語言在并、連接及星號(hào)運(yùn)算下的閉包。定理2.3.1

有窮自動(dòng)機(jī)接受的語言類在下述運(yùn)算下是封閉的：

a.并 b.連c.Kleene星號(hào)d.補(bǔ)e.交[證明]

（注：采用構(gòu)造性證明）a.并，設(shè)兩臺(tái)非確定性自動(dòng)機(jī)M1、M2，構(gòu)造一臺(tái)M使得L(M)=L(M1)∪L(M)圖示P47b.連接，設(shè)兩臺(tái)非確定性自動(dòng)機(jī)M1、M2，構(gòu)造一臺(tái)M使得L(M)=L(M1)○L(M)圖示P48c.星號(hào)，設(shè)一臺(tái)非確定性自動(dòng)機(jī)M1，構(gòu)造一臺(tái)M使得L(M)=L(M1)*圖示見P48d.補(bǔ)，設(shè)一臺(tái)確定性自動(dòng)機(jī)M=

(K,,,s,F)，補(bǔ)語言L’=*-L(M)被確定自動(dòng)機(jī)M’=

(K,,,s,K-F)接受。也就是M和M’完全一樣，只交換終結(jié)狀態(tài)與非終結(jié)狀態(tài)。e.交，因?yàn)?，L1∩L2=*-((*-L1)∪(*-L2))，故由并和補(bǔ)下封閉性，得交下封閉。定理2.3.2

一個(gè)語言是正則的當(dāng)且僅當(dāng)它被有窮自動(dòng)機(jī)接受。

（注：僅當(dāng)---利用定理2.3.1證明；當(dāng)---利用歸納證明）例2.3.1

考慮正則語言(ab∪aab)*。用定理2.3.1各部分證明中的方法構(gòu)造一臺(tái)非確定型有窮自動(dòng)機(jī)接受這個(gè)正則表達(dá)式所表示的語言。解：按一下幾步構(gòu)造之。階段1aba;bb階段2aebaeaeab;aab階段3aebbaeaeeeab∪aab階段4：(ab∪aab)*aebaeaebeeeee例2.3.2

構(gòu)造圖中確定型有窮自動(dòng)機(jī)接受的語言的正則表達(dá)式。這臺(tái)自動(dòng)機(jī)接受語言為：babbaa假定:

NFA具有如下性質(zhì)：

(1)它有唯一的終結(jié)狀態(tài)，F(xiàn)={f}(2)沒有進(jìn)入初始狀態(tài)的轉(zhuǎn)移和離開終結(jié)狀態(tài)的轉(zhuǎn)移。解：按以下步驟可以得到相應(yīng)的正則表達(dá)式。babbaee步驟1：改造之符合性質(zhì)abaae步驟2：消除狀態(tài)q1e步驟3：消除狀態(tài)q2步驟4：消除狀態(tài)q3討論：習(xí)題2.3.72.4正則語言與非正則語言

前面已經(jīng)證實(shí)，正則語言在各種運(yùn)算下封閉，可以用正則表達(dá)式及確定型或非確定型有窮自動(dòng)機(jī)說明，這些事實(shí)給我們提供了證明語言是正則的各種技術(shù)。

例2.4.1

設(shè)∑＝{0,1…,9}，L∑*是可以被2或3整除的非負(fù)整數(shù)的十進(jìn)制表示的集合（前面無多余的0）。例如，0，3，6，244∈L，而1，03，00L。L是正則的。[證明]

我們通過這個(gè)例子來說明通過正則語言的封閉性證明一個(gè)語言是正則的方法。

L=L2∪L3

其中：L2為可以被2整除的非負(fù)整數(shù)的十進(jìn)制表示的集合L3為可以被3整除的非負(fù)整數(shù)的十進(jìn)制表示的集合第一步證明非負(fù)整數(shù)的十進(jìn)制表示是正則的： 設(shè)L1是非負(fù)整數(shù)的十進(jìn)制表示，則：L1＝0U{1,2,…,9}∑*

由于L1是用正則表達(dá)式表示的，故L1是一個(gè)正則語言。第二步再證明L2（被2整除的非負(fù)整數(shù)十進(jìn)制數(shù)集合）是正則的。

L2是以0，2，4，6，8結(jié)尾的L1的成員組成的集合，即，

L2＝L1∩∑*{0,2,4,6,8}

根據(jù)定理2.3.1(e)（有窮自動(dòng)機(jī)接受的語言在交運(yùn)算下是封閉的），可知L2是正則的。第三步證明L3（被3整除的非負(fù)整數(shù)十進(jìn)制數(shù)集合）是正則的。 可以被3整除的非負(fù)整數(shù)需要滿足的條件是它的數(shù)字之和可以被3整除。 我們可以構(gòu)造一臺(tái)有窮自動(dòng)機(jī)，用它的有窮控制器保存每個(gè)輸入數(shù)字的模3之和。（定理2.3.2）如下頁圖所示。

L3是這臺(tái)有窮自動(dòng)機(jī)接受的語言與L1的交，則L3也是正則的。最后，L＝L2UL3，則L也是正則的。

L是一個(gè)正則語言。<證明完畢>1，4，72，5，81，4，71，4，72，5，82，5，80，3，6，90，3，6，90，3，6，9(余1)(余2)(余0)圖被3整除的非負(fù)整數(shù)集合L3說明：雖然有各種強(qiáng)力技術(shù)證明語言是正則的，但還沒有辦法證明語言不是正則的。非正則語言是存在的——因?yàn)?正則表達(dá)式(和有窮自動(dòng)機(jī))的數(shù)目是可數(shù)的 語言的數(shù)目是不可數(shù)的

定理2.4.1

設(shè)L是一個(gè)正則語言，則存在正整數(shù)n≥1使得任一字符串ω∈L只要|ω|≥n就可以寫成ω＝xyz，其中y≠e，|xy|≤n且對(duì)每一個(gè)i≥0，xyiz∈L。

[證明]（注：引用p14頁鴿巢原理證明）因?yàn)長是正則語言，故L可被一臺(tái)確定性有窮自動(dòng)機(jī)M接受。設(shè)M有n個(gè)狀態(tài)，考慮M對(duì)|ω|≥n的前n步計(jì)算：

(q0,w1w2…wn)├M

(q1,w2w3…wn)├M

…├M(qn,e)其中q0是初始狀態(tài)這里有n+1個(gè)格局，M有n狀態(tài)，據(jù)鴿巢原理q0q1…qn中必然有狀態(tài)重復(fù)出現(xiàn)，qi=qji<j，對(duì)應(yīng)字符串wi+1…wj=y,x=w1..wi,z=wj+1…n，顯然成立。證明完畢。

理解：這是泵定理之一，斷言在某些字符串中存在某些點(diǎn)，可以在這些地方重復(fù)插入一個(gè)子串而不影響字符串的接受性。根據(jù)這個(gè)定理我們可以確定一個(gè)語言是非正則語言。例2.4.4

有時(shí)候也用封閉性證明一個(gè)語言不是正則的。例如：L={ω∈{a,b}*:ω中a和b的個(gè)數(shù)相同}不是正則的。因?yàn)槿绻鸏是正則的，則根據(jù)在交運(yùn)算下的封閉性，L∩a*b*也是封閉的。而后者正好是{anbn:n≥0}，剛剛證明不是正則的。所以與假設(shè)沖突，L不是正則的。討論：習(xí)題2.4.8例2.4.2

語言L＝{anbn:i≥0}不是正則的。假定L是正則的，則存在滿足定理2.4.1要求的整數(shù)n?？紤]字符串ω＝anbn∈L。根據(jù)定理，可以把它重寫誠ω＝xyz使得|xy|≤n且y≠e，即y＝ai，其中i>0。但是，xz＝an-ibn

L，與定理矛盾。2.5狀態(tài)最小化最簡單的優(yōu)化： 給定一臺(tái)確定型有窮自動(dòng)機(jī)，刪去所有不可達(dá)的狀態(tài)及所有進(jìn)入或離開它們的轉(zhuǎn)移。刪去不可達(dá)的狀態(tài)的方法是從初始狀態(tài)開始求出可達(dá)狀態(tài)的集合。下面給出求可達(dá)狀態(tài)的集合的算法：

R:={s}; While存在狀態(tài)p∈R和a∈∑使δ(p,a)R do把δ(p,a)加入R。例如書上p58圖2-19中q7q8是明顯不可達(dá)的，消除后剩下的自動(dòng)機(jī)如圖2-20。如下左邊