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

緒論課程信息為什么學(xué)習(xí)形式語(yǔ)言與自動(dòng)機(jī)形式語(yǔ)言與自動(dòng)機(jī)概述及應(yīng)用課程內(nèi)容及要求1-緒論課程信息1-

專(zhuān)業(yè)基礎(chǔ)課

上世紀(jì)60年代末、70年代初，研究的高峰

之后，向應(yīng)用領(lǐng)域滲透，研究生課程

近幾年，本科階段的專(zhuān)業(yè)基礎(chǔ)課

專(zhuān)業(yè)工作者必須的理論素養(yǎng)

計(jì)算模型計(jì)算機(jī)（不）能夠做什么問(wèn)題分類(lèi)計(jì)算的復(fù)雜性，算法分析形式系統(tǒng)建模工具（狀態(tài)機(jī)）抽象描述形式文法、形式表達(dá)式

課程性質(zhì)2-專(zhuān)業(yè)基礎(chǔ)課課程性質(zhì)2-相關(guān)課程先修課程

《離散數(shù)學(xué)》（《數(shù)理邏輯》，《集合論》）計(jì)算機(jī)導(dǎo)論與程序設(shè)計(jì)、數(shù)據(jù)結(jié)構(gòu)

后續(xù)課程

《編譯原理》

其它相關(guān)課程《模式識(shí)別》、《算法分析》3-相關(guān)課程先修課程3-教材： 形式語(yǔ)言與自動(dòng)機(jī) 王柏楊娟

編著 北京郵電大學(xué)出版社2003.14-教材：4-經(jīng)典參考書(shū)

書(shū)名

IntroductiontoAutomataTheory,Languages,andComputation（SecondEdition）

作者

JohnE.Hopcroft（Cornell）RajeevMotwani（Stanford）JeffereyD.Ullman（Stanford）

出版社

AddisonWesley（2001）

清華大學(xué)出版社（影印版）FirstEdition

中譯本《自動(dòng)機(jī)理論、語(yǔ)言和計(jì)算導(dǎo)引》徐美瑞等譯科學(xué)出版社，1990

John.E.Hopcroft,theTuringAwardwinnerin1986.5-經(jīng)典參考書(shū)書(shū)名Introductio其它參考書(shū)

《自動(dòng)機(jī)理論及其應(yīng)用》何成武科學(xué)出版社1990《形式語(yǔ)言及其句法分析》美A.V.阿霍等科學(xué)出版社1987《形式語(yǔ)言》王兵山，吳兵編國(guó)防工業(yè)大學(xué)出版社，1988

《形式語(yǔ)言與自動(dòng)機(jī)》陳有祺編著南開(kāi)大學(xué)出版社，天津，1999

6-其它參考書(shū)《自動(dòng)機(jī)理論及其應(yīng)用》6-2、為什么學(xué)習(xí)形式語(yǔ)言與自動(dòng)機(jī)形式語(yǔ)言與自動(dòng)機(jī)是計(jì)算機(jī)科學(xué)的基礎(chǔ)理論之一，是計(jì)算機(jī)學(xué)科的專(zhuān)業(yè)基礎(chǔ)課。在人工智能、電信領(lǐng)域等有廣泛的應(yīng)用。通過(guò)一些定理的證明和應(yīng)用，對(duì)大家進(jìn)行思維訓(xùn)練，從而為今后學(xué)習(xí)通信軟件，協(xié)議工程，編譯技術(shù)，人工智能等內(nèi)容提供理論基礎(chǔ)。7-2、為什么學(xué)習(xí)形式語(yǔ)言與自動(dòng)機(jī)形式語(yǔ)言與自動(dòng)機(jī)是計(jì)算機(jī)科學(xué)的2、為什么學(xué)習(xí)形式語(yǔ)言與自動(dòng)機(jī)對(duì)客觀世界的科學(xué)研究：目的在于把抽象數(shù)學(xué)的形式化體系發(fā)展成為與現(xiàn)實(shí)生活相似的理論模型，從而提供一種通用結(jié)構(gòu)來(lái)描述、理解和解決問(wèn)題。計(jì)算機(jī)科學(xué)：是關(guān)于計(jì)算知識(shí)的有系統(tǒng)的整體。8-2、為什么學(xué)習(xí)形式語(yǔ)言與自動(dòng)機(jī)對(duì)客觀世界的科學(xué)研究：目的在于2、為什么學(xué)習(xí)形式語(yǔ)言與自動(dòng)機(jī)計(jì)算機(jī)科學(xué)的兩個(gè)主要部分：構(gòu)成計(jì)算基礎(chǔ)的一些基本概念和模型；設(shè)計(jì)計(jì)算系統(tǒng)(軟件和硬件)的工程技術(shù)（設(shè)計(jì)理論的應(yīng)用）本課程著重介紹第一部分（涉及到一些第二部分的應(yīng)用），通過(guò)形式化技術(shù)對(duì)大家進(jìn)行思維訓(xùn)練，為今后的學(xué)習(xí)打好理論基礎(chǔ)。9-2、為什么學(xué)習(xí)形式語(yǔ)言與自動(dòng)機(jī)計(jì)算機(jī)科學(xué)的兩個(gè)主要部分：9-3、形式語(yǔ)言與自動(dòng)機(jī)概述及應(yīng)用本門(mén)課程將圍繞著什么是形式語(yǔ)言、什么是自動(dòng)機(jī)、以及形式語(yǔ)言和自動(dòng)機(jī)的相互關(guān)系進(jìn)行闡述。核心內(nèi)容

有限狀態(tài)自動(dòng)機(jī)，正規(guī)語(yǔ)言，正規(guī)表達(dá)式上下文無(wú)關(guān)文法，上下文無(wú)關(guān)語(yǔ)言，下推自動(dòng)機(jī)圖靈機(jī)，計(jì)算問(wèn)題分類(lèi)10-3、形式語(yǔ)言與自動(dòng)機(jī)概述及應(yīng)用本門(mén)課程將圍繞著什么是形式語(yǔ)言3.1

形式語(yǔ)言什么是形式語(yǔ)言形式語(yǔ)言:形式化描述的字母表上的字符串的集合。字母表：字符的有限集合。e.g.：26個(gè)英文字母構(gòu)成的字母表。字符串：字母表中的字符構(gòu)成的有限序列。e.g.hello,afjhkfyu

11-3.1形式語(yǔ)言什么是形式語(yǔ)言11-為什么用形式語(yǔ)言自然語(yǔ)言：人們平時(shí)說(shuō)話時(shí)所使用的一種語(yǔ)言，不同的國(guó)家和民族有著不同的語(yǔ)言。形式語(yǔ)言通過(guò)人們公認(rèn)的符號(hào)，表達(dá)方式所描述的一種語(yǔ)言，是一種通用語(yǔ)言，沒(méi)有國(guó)籍之分。形式語(yǔ)言是某個(gè)字母表上的字符串的集合，有一定的描述范圍。12-為什么用形式語(yǔ)言自然語(yǔ)言：人們平時(shí)說(shuō)話時(shí)所使用的一種語(yǔ)言，不為什么用形式語(yǔ)言例1：漢語(yǔ)：<主><謂><賓>――用數(shù)字、符號(hào)等形式化的東西來(lái)描述語(yǔ)言我吃飯――語(yǔ)法正確我飯吃――語(yǔ)法錯(cuò)誤飯吃我――語(yǔ)法正確，語(yǔ)義錯(cuò)誤13-為什么用形式語(yǔ)言例1：漢語(yǔ)：<主><謂><賓>為什么用形式語(yǔ)言例2：T為PASCAL語(yǔ)言所用的全部符號(hào)的集合。正確的PASCAL程序就是T上的語(yǔ)言。例3：在字母表T={a}上，L={a2n+1|n>=0}表示任意一對(duì)aa(包括0對(duì))后跟一個(gè)a的字符串。（即含有奇數(shù)個(gè)a的字符串。）14-為什么用形式語(yǔ)言例2：T為PASCAL語(yǔ)言所用的全部符號(hào)的集為什么用形式語(yǔ)言形式語(yǔ)言的最初起因：語(yǔ)言學(xué)家（Chomsky）想用一套形式化方法來(lái)描述語(yǔ)言。形式語(yǔ)言在自然語(yǔ)言研究中起步，在計(jì)算機(jī)科學(xué)中得到廣泛應(yīng)用。最初的應(yīng)用：編譯――讓計(jì)算機(jī)按照語(yǔ)法規(guī)則將高級(jí)語(yǔ)言方便地翻譯成機(jī)器語(yǔ)言。15-為什么用形式語(yǔ)言形式語(yǔ)言的最初起因：語(yǔ)言學(xué)家（Chomsk為什么用形式語(yǔ)言現(xiàn)在：已廣泛應(yīng)用在人工智能、圖象處理、通信協(xié)議、通信軟件等多個(gè)領(lǐng)域在計(jì)算機(jī)理論科學(xué)方面：是可計(jì)算理論（算法―在有限步驟內(nèi)求得解、算法復(fù)雜性、停機(jī)問(wèn)題、）、定理自動(dòng)證明、程序轉(zhuǎn)換（程序自動(dòng)生成）、模式識(shí)別等的基礎(chǔ)。16-為什么用形式語(yǔ)言現(xiàn)在：已廣泛應(yīng)用在人工智能、圖象處理、通信為什么用形式語(yǔ)言比爾.蓋茨：人類(lèi)計(jì)算的未來(lái)是讓計(jì)算機(jī)能夠看、聽(tīng)、學(xué)，能用自然語(yǔ)言與人類(lèi)交流形式化非常重要17-為什么用形式語(yǔ)言比爾.蓋茨：人類(lèi)計(jì)算的未來(lái)是讓計(jì)算機(jī)能夠看、

3.2.自動(dòng)機(jī)什么是自動(dòng)機(jī)？具有離散輸入輸出的數(shù)學(xué)模型。包括：輸入裝置 讀頭+輸入帶控制部件。

狀態(tài)轉(zhuǎn)移存儲(chǔ)單元大量通信軟件的基本工作機(jī)制都是有限狀態(tài)自動(dòng)機(jī)。自動(dòng)機(jī)理論在通信領(lǐng)域中的應(yīng)用極為廣泛。18-3.2.自動(dòng)機(jī)什么是自動(dòng)機(jī)？18-

3.2.自動(dòng)機(jī)自動(dòng)機(jī)接受一定的輸入，執(zhí)行一定的動(dòng)作，產(chǎn)生一定的結(jié)果。使用狀態(tài)遷移描述整個(gè)工作過(guò)程。狀態(tài)：一個(gè)標(biāo)識(shí)，能區(qū)分自動(dòng)機(jī)在不同時(shí)刻的狀況。有限狀態(tài)系統(tǒng)具有任意有限數(shù)目的內(nèi)部“狀態(tài)”自動(dòng)機(jī)的本質(zhì)：根據(jù)狀態(tài)、輸入和規(guī)則決定下一個(gè)狀態(tài)狀態(tài)＋輸入（激勵(lì)）＋規(guī)則―>狀態(tài)遷移19-3.2.自動(dòng)機(jī)自動(dòng)機(jī)接受一定的輸入，執(zhí)行一定的動(dòng)作，產(chǎn)生為什么叫自動(dòng)機(jī)？可能的狀態(tài)、運(yùn)行的規(guī)則都是事先確定的。一旦開(kāi)始運(yùn)行，就按照事先確定的規(guī)則工作，因此叫“自動(dòng)機(jī)”。有限自動(dòng)機(jī)可以認(rèn)為是由一個(gè)帶有讀頭的有限控制器和一條寫(xiě)有字符的輸入帶組成。20-為什么叫自動(dòng)機(jī)？可能的狀態(tài)、運(yùn)行的規(guī)則都是事先確定的。一旦開(kāi)自動(dòng)機(jī)舉例例1：打電話(自動(dòng)機(jī)在通信領(lǐng)域的應(yīng)用)。

在一次呼叫中，從建立連接到通話完畢，要經(jīng)歷摘機(jī)，撥號(hào)，應(yīng)答，進(jìn)行通話等過(guò)程，可以分別用四個(gè)狀態(tài)來(lái)表示。q0q1q2q3q4摘機(jī)收到撥號(hào)音撥號(hào)收應(yīng)答信號(hào)掛機(jī)收齊號(hào)碼q0:空閑狀態(tài)q1:等待撥號(hào)狀態(tài)q2:可以撥號(hào)狀態(tài)q3:等待應(yīng)答狀態(tài)q4:通話狀態(tài)21-自動(dòng)機(jī)舉例例1：打電話(自動(dòng)機(jī)在通信領(lǐng)域的應(yīng)用)。q0q1自動(dòng)機(jī)舉例例2：串口通信 兩臺(tái)微機(jī)通過(guò)串口通信,需在兩臺(tái)機(jī)器間建立好連接后，才可以傳遞數(shù)據(jù)，可以使用有限狀態(tài)自動(dòng)機(jī)，描述串口通信的狀態(tài)。傳輸數(shù)據(jù)收到應(yīng)答斷開(kāi)連接連接請(qǐng)求q0q1q222-自動(dòng)機(jī)舉例例2：串口通信傳輸數(shù)據(jù)收到斷開(kāi)連接請(qǐng)求q0q1q2自動(dòng)機(jī)舉例例3。在許多數(shù)字電子技術(shù)基礎(chǔ)教科書(shū)中，串行序列檢測(cè)電路設(shè)計(jì)常常被作為同步時(shí)序電路設(shè)計(jì)的一個(gè)例題。要求設(shè)計(jì)“111”序列檢測(cè)電路。它要求電路有一個(gè)串行輸入端X及一個(gè)串行輸出端Z，當(dāng)輸入序列連續(xù)輸入3個(gè)1時(shí)，輸出為1，否則輸出為0。23-自動(dòng)機(jī)舉例例3。在許多數(shù)字電子技術(shù)基礎(chǔ)教科書(shū)中，串行序列檢測(cè)24-24-自動(dòng)機(jī)的分類(lèi)根據(jù)結(jié)構(gòu)不同，自動(dòng)機(jī)又可分為有限自動(dòng)機(jī)，下推自動(dòng)機(jī)，圖靈機(jī)等。下推自動(dòng)機(jī)可以看作是由一條輸入帶，一個(gè)有限控制器和一個(gè)下推棧組成?；緢D靈機(jī)由一個(gè)具有讀寫(xiě)頭的有限控制器和一條無(wú)限帶組成。使用自動(dòng)機(jī)，可以形式化的描述現(xiàn)實(shí)世界中的一些問(wèn)題。25-自動(dòng)機(jī)的分類(lèi)根據(jù)結(jié)構(gòu)不同，自動(dòng)機(jī)又可分為有限自動(dòng)機(jī)，下推自動(dòng)3.3形式語(yǔ)言與自動(dòng)機(jī)的關(guān)系形式語(yǔ)言和自動(dòng)機(jī)是密切相關(guān)的。形式語(yǔ)言――字符串自動(dòng)機(jī)――字符串的識(shí)別系統(tǒng)根據(jù)復(fù)雜程度可將形式語(yǔ)言分類(lèi)，根據(jù)自動(dòng)機(jī)的接受能力、處理能力的不同也將自動(dòng)機(jī)分類(lèi)。二者之間具有較好的對(duì)應(yīng)關(guān)系。26-3.3形式語(yǔ)言與自動(dòng)機(jī)的關(guān)系形式語(yǔ)言和自動(dòng)機(jī)是密切相關(guān)的。3.3形式語(yǔ)言與自動(dòng)機(jī)的關(guān)系27-3.3形式語(yǔ)言與自動(dòng)機(jī)的關(guān)系27-語(yǔ)言與有限自動(dòng)機(jī)（FiniteAutomata）設(shè)=0,1，L=ww中至少有一個(gè)0，如0011,10,110111

L,而11,,1111

L。下圖是一個(gè)可接受該語(yǔ)言的有限狀態(tài)自動(dòng)機(jī)28-語(yǔ)言與有限自動(dòng)機(jī)（FiniteAutomata）小結(jié)文法是定義語(yǔ)言的一個(gè)數(shù)學(xué)模型，而自動(dòng)機(jī)可看作是語(yǔ)言的識(shí)別系統(tǒng)。通過(guò)對(duì)一些定理的證明，說(shuō)明對(duì)于一個(gè)文法產(chǎn)生的語(yǔ)言，可以構(gòu)造相應(yīng)自動(dòng)機(jī)接受該語(yǔ)言：一個(gè)自動(dòng)機(jī)接受的語(yǔ)言，可以構(gòu)造對(duì)應(yīng)的文法產(chǎn)生該語(yǔ)言。一定類(lèi)型的自動(dòng)機(jī)和某種類(lèi)型的文法具有等價(jià)性。29-小結(jié)文法是定義語(yǔ)言的一個(gè)數(shù)學(xué)模型，而自動(dòng)機(jī)可看作是語(yǔ)言的識(shí)別課程內(nèi)容及要求課程內(nèi)容：書(shū)上二、三、四、五、六章。要求：通過(guò)本課學(xué)習(xí)，要求同學(xué)們掌握形式化描述方法，建立起形式語(yǔ)言與自動(dòng)機(jī)的概念，并能在實(shí)際中加以應(yīng)用。通過(guò)對(duì)定理的證明，對(duì)同學(xué)們進(jìn)行思維訓(xùn)練，并掌握一定的證明方法。30-課程內(nèi)容及要求課程內(nèi)容：書(shū)上二、三、四、五、六章。30-證明技術(shù)*定義、定理和證明基本證明方法歸納證明技術(shù)*

引自清華大學(xué)計(jì)算機(jī)系軟件技術(shù)研究所王生原老師課件31-證明技術(shù)*定義、定理和證明*引自清華大學(xué)計(jì)算機(jī)系軟定義、定理和證明定義：對(duì)象和概念的描述。定義需要精確，明確說(shuō)明對(duì)象的構(gòu)成。命題：描述某個(gè)對(duì)象所具有的某種性質(zhì)。也需精確。證明：邏輯論證，確認(rèn)一個(gè)命題為真。定理：被證明為真的（數(shù)學(xué)）命題。引理：被證明的命題，有助于證明另一個(gè)更有意義的命題32-定義、定理和證明定義：對(duì)象和概念的描述。定義需要精確，明確說(shuō)演繹證明

概念一個(gè)證明（proof）是命題的序列，其中的每一個(gè)命題或者是已知的命題，或者是由前面出現(xiàn)過(guò)的命題使用邏輯公理和規(guī)則得出.已知的命題集合稱(chēng)為假設(shè)（hypothesis）或前提（premise），最后一個(gè)命題稱(chēng)為該前提的結(jié)論（conclusion）.

33-演繹證明概念一個(gè)證明（proof）是命題的序“If–Then”命題

證明方法把If

部分作為已知的命題，把Then

部分作為結(jié)論.

舉例如果x+y=1，那么x2-y2=x-y.

證明:1x2-y2=(x+y)(x-y)//數(shù)學(xué)公理2(x+y)

=1//已知x2-y2=x-y//由1、2和算術(shù)性質(zhì)推出34-“If–Then”命題證明方法1x2-y2“If-And-Only-If”命題欲證AifandonlyifB，

可分別證明如下兩個(gè)命題：

1

ifAthenB，

2

ifBthenA.

35-“If-And-Only-If”命題欲證有關(guān)集合的命題在本課程中，經(jīng)常要證明兩種不同方法構(gòu)造的集合是相同的集合（比如語(yǔ)言表達(dá)的等價(jià)性）。設(shè)R,S為集合的表達(dá)式，下面兩個(gè)命題的證明需要參照集合的定義，分別表示為如下的命題。

欲證RS，可證明如下命題：

ifxRthenxS

欲證R=S，可分別證明如下兩個(gè)命題：

1

ifxRthenxS

2

ifxSthenxR36-有關(guān)集合的命題在本課程中，經(jīng)常要證明兩種不同方法構(gòu)造的集合原命題的逆否命題有時(shí)，證明原命題的逆否(contrapositive)命題更加方便.

欲證ifAthenB，

可證明如下命題：

ifnotBthennotA原因：兩個(gè)命題是等價(jià)，（蘊(yùn)涵邏輯等價(jià)）。37-原命題的逆否命題有時(shí)，證明原命題的逆否(contraposi反證法

反證（proofbycontradiction）

欲證ifHthenC，可以把H和notC都作為已知的命題，把任何一個(gè)矛盾(contradiction)命題作為新的結(jié)論.38-反證法反證（proofbycontradiction）舉例證明或否證

舉例證明存在量化的命題如命題：存在整數(shù)a，滿足a2=2a.

證明:取a=2.，滿足a2=2a.

舉反例否定全稱(chēng)量化的命題如命題：所有整數(shù)a，都滿足a2=2a.

否證:取a=1.，不滿足a2=2a.39-舉例證明或否證舉例證明存在量化的命題39-

歸納證明在處理遞歸定義的對(duì)象時(shí)“必不可少”。在自動(dòng)機(jī)理論中，需要?dú)w納證明處理遞歸定義的概念，比如：樹(shù)、表達(dá)式等。歸納法原理：如果證明了S(i),并且證明了對(duì)所有n≥i，S(n)蘊(yùn)涵S(n+1)，就可得出：對(duì)所有n≥i,S(n)成立。歸納證明與遞歸定義的對(duì)應(yīng)。歸納證明與結(jié)構(gòu)歸納法40-歸納證明在處理遞歸定義的對(duì)象時(shí)“必不可少”。在自動(dòng)機(jī)理論中歸納證明與結(jié)構(gòu)歸納法集合的遞歸定義由3部分構(gòu)成：

1基礎(chǔ)（basis）//直接定義集合中的元素（至少1個(gè)）

2歸納（induction）//從已知元素生成新元素的規(guī)則

3極小性限制//申明集合中的元素只能由1、2生成

41-歸納證明與結(jié)構(gòu)歸納法集合的遞歸定義41-歸納證明與結(jié)構(gòu)歸納法結(jié)構(gòu)歸納法對(duì)于歸納（遞歸）定義的集合S，欲證對(duì)于任意xS，滿足性質(zhì)P(x).

1基礎(chǔ)（basis）//若有直接定義aS，則證明P(a)

2歸納（induction）//若歸納定義中有規(guī)則

ifa1,a2,,anSthenf(a1,a2,,an)S，則證明

ifP(a1),P(a2),,P(an)SthenP(f(a1,a2,,an))42-歸納證明與結(jié)構(gòu)歸納法結(jié)構(gòu)歸納法42-

歸納定義合法括號(hào)串的集合S

1基礎(chǔ)空串S

2歸納若xS，則(x)S；

若x,yS，則xyS.

3極小性限制S中的元素只能由1、2生成(或：S是滿足1、2的最小集合)

命題：合法括號(hào)串集合S中每個(gè)括號(hào)串的“(”與“)”數(shù)目相等

證明:

1基礎(chǔ)空串的“(”與“)”數(shù)目相等，都為0；

2歸納設(shè)x,y的“(”與“)”數(shù)目相等，前者為m，后者為n；

(x)的“(”與“)”數(shù)目都為m+1；

xy的“(”與“)”數(shù)目都為m+n.歸納定義與結(jié)構(gòu)歸納證明（例）43-歸納定義合法括號(hào)串的集合S歸納定義與結(jié)構(gòu)歸納證明（例）4

自然數(shù)自然數(shù)集合N是滿足如下條件的最小集合：

(1)0

N;(2)若

nN,則n的后繼n+1N

數(shù)學(xué)歸納法欲證對(duì)任意自然數(shù)n，P(n)成立，(1)先證

P(0)成立;(2)再證若

P(n)成立,則P(n+1)成立

另一種形式

(1)先證P(0)成立;(2)再證若對(duì)任意k<n，P(k)成立,則P(n)成立

對(duì)任何良序集合，都可以有這兩種形式基于自然數(shù)的歸納—一般數(shù)學(xué)歸納法44-自然數(shù)自然數(shù)集合N是滿足如下條件的最小集合：基于自然第二章語(yǔ)言及文法主要內(nèi)容：定義形式語(yǔ)言的術(shù)語(yǔ)給出文法的定義和文法的分類(lèi)要求掌握：語(yǔ)言和文法的形式定義CHOMSKY文法體系的分類(lèi)。45-第二章語(yǔ)言及文法主要內(nèi)容：45-第一節(jié)語(yǔ)言的定義與運(yùn)算一、語(yǔ)言的一些術(shù)語(yǔ)：

字母表：字符的有限集合，記為T(mén)。字符串：由字母表T中的字符構(gòu)成的序列稱(chēng)字母表T上的字符串（句子）。常記為u,v,w,x,y,z；

常用a,b,c,d標(biāo)識(shí)單個(gè)字符。46-第一節(jié)語(yǔ)言的定義與運(yùn)算一、語(yǔ)言的一些術(shù)語(yǔ)：46-字母表（Alphabet）

概念

形式符號(hào)的集合

記號(hào)常用T、表示

舉例英文字母表a,b,…,z,A,B,…,Z

英文標(biāo)點(diǎn)符號(hào)表,;:.?!’‘“”()…漢字表…,自,…,動(dòng),…,機(jī),…

化學(xué)元素表H,He,Li,…,

T=a,n,y,任,意47-字母表（Alphabet）概念形式符號(hào)的集合4字符串（string）

概念字母表T上的一個(gè)字符串（簡(jiǎn)稱(chēng)串），或稱(chēng)為字（word），為T(mén)

中字符構(gòu)成的一個(gè)有限序列。

空串（emptystring）,用表示，不包含任何字符。

舉例設(shè)T=a,b，則

,

a,ba,bbaba等都是串

字符串w

的長(zhǎng)度，記為w，是包含在w中字符的個(gè)數(shù)

舉例=0，bbaba=5ai

表示含有i個(gè)a的字符串

48-字符串（string）概念字母表T上的一個(gè)

連接（concatenation）

設(shè)x,y為串,且xa1a2…am,yb1b2…bn,則x與y的連接

xya1a2…amb1b2…bn

連接運(yùn)算的性質(zhì)

(xy)z

x（yz

）

xxx

xyx+y

關(guān)于字符串的運(yùn)算49-連接（concatenation）關(guān)于字符串

其它如取頭字符，取尾部，子串匹配

等

設(shè)ω1,ω2,ω3是字母表T上的字符串，稱(chēng)：ω1是字符串ω1ω2的前綴，ω2是字符串ω1ω2的后綴，ω2是字符串ω1ω2ω3的子串?？沾侨魏巫址那熬Y，后綴及子串。

例：abc的前綴aababcε.后綴cbcabcε.子串a(chǎn)bcabbcabcε,

即一個(gè)字符串可以看作是多個(gè)字符串的連接。

關(guān)于字符串的運(yùn)算50-其它如取頭字符，取尾部，子串匹配等關(guān)于字字符串ω的逆用表示。是字符串ω的倒置。ω=b1b2……bn=bnbn-1……b2b1

空串ε的逆還是ε51-字符串ω的逆用表示。是字符串ω的倒置。51-字母表的冪運(yùn)算

冪運(yùn)算

Tn

用來(lái)表示該字母表長(zhǎng)度為n的所有串的集合。設(shè)T為字母表，n為任意自然數(shù)，定義（1）T0=（2）設(shè)x

Tn-1，a

T，則a

x

Tn（3）

Tn中的元素只能由（1）和（2）生成

閉包

T*=

T0T1T2…

閉包

T+=

T1T2T3…

T*=T+，T+=T*

52-字母表的冪運(yùn)算冪運(yùn)算Tn用來(lái)表示該字母表閉包的物理意義

T的星號(hào)閉包T*：字母表T上的所有字符串和空串的集合。

T的正閉包T+：字母表T上的所有字符串構(gòu)成的集合。 T*=T+∪{ε}舉例設(shè)T=0，1，則

T0=，T1=0，1，T2=00，01，10，11，…

T*=，0，1，00，01，10，11，…

T+=

0，1，00，01，10，11，…53-閉包的物理意義T的星號(hào)閉包T*：字母表T上的所有字符串語(yǔ)言（Languages）

概念設(shè)T為字母表，則任何集合LT*是字母表T上的一個(gè)語(yǔ)言（language）

舉例

英文單詞集…,English,…,words,…

C

語(yǔ)言程序集…字母表？漢語(yǔ)成語(yǔ)集…,馬到成功,…

化學(xué)分子式集…,H2O,…,NaCl,…

any,任意

54-語(yǔ)言（Languages）概念設(shè)T為字母表語(yǔ)言（Languages）舉例：設(shè)T={a，b}則L1={anbn|n≥1}L3={bk|k是質(zhì)數(shù)}L2={ε}只有一個(gè)空句子的語(yǔ)言L4={}=Φ空語(yǔ)言均為字母表T上的語(yǔ)言。由語(yǔ)言的定義知語(yǔ)言是集合，對(duì)于集合的運(yùn)算可應(yīng)用于對(duì)于語(yǔ)言的計(jì)算。如并，交，補(bǔ)，差。55-語(yǔ)言（Languages）舉例：設(shè)T={a，b}語(yǔ)言的基本運(yùn)算語(yǔ)言的積：

兩個(gè)語(yǔ)言L1和L2的積L1L2是由L1和L2中的字符串連接所構(gòu)成的字符串的集合。即L1中所有字符串分別與L2中的字符串連接得到的集合。設(shè)T={a,b}，L1和L2是T上的語(yǔ)言。L1={ab,ba}L2={aa,bb}則L1L2={abaa,abbb,baaa,babb}L2L1={aaab,aaba,bbab,bbba}L1L2≠L2L1

語(yǔ)言的積不可交換。56-語(yǔ)言的基本運(yùn)算語(yǔ)言的積：56-語(yǔ)言的基本運(yùn)算語(yǔ)言的冪： 語(yǔ)言的冪可歸納定義如下: L0={ε}Ln=L·Ln-1=Ln-1·Ln≥1上例中，L12={abab,abba,baab,baba}L22={aaaa,aabb,bbaa,bbbb}

57-語(yǔ)言的基本運(yùn)算語(yǔ)言的冪：57-第二節(jié)文法定義：所謂文法是用來(lái)定義語(yǔ)言的一個(gè)數(shù)學(xué)模型表示語(yǔ)言的方法：若語(yǔ)言L是有限集合，可用列舉法若L是無(wú)限集合（集合中的每個(gè)元素有限長(zhǎng)度），用其他方法。方法一：文法產(chǎn)生系統(tǒng)，由定義的文法規(guī)則產(chǎn)生出語(yǔ)言的每個(gè)句子方法二：機(jī)器識(shí)別系統(tǒng)：當(dāng)一個(gè)字符串能被一個(gè)語(yǔ)言的識(shí)別系統(tǒng)接受，則這個(gè)字符串是該語(yǔ)言的一個(gè)句子，否則不屬于該語(yǔ)言。58-第二節(jié)文法定義：所謂文法是用來(lái)定義語(yǔ)言的一個(gè)數(shù)學(xué)模型5元語(yǔ)言定義：描述語(yǔ)言的語(yǔ)言 例如：各種各樣的程序設(shè)計(jì)語(yǔ)言當(dāng)人們要解釋或討論程序設(shè)計(jì)語(yǔ)言本身時(shí)，又需要一種語(yǔ)言，被討論的語(yǔ)言叫做對(duì)象語(yǔ)言，即某種程序設(shè)計(jì)語(yǔ)言，討論對(duì)象語(yǔ)言的語(yǔ)言稱(chēng)為元語(yǔ)言。59-元語(yǔ)言定義：描述語(yǔ)言的語(yǔ)言59-BNF（巴科斯范式） BNF范式通常被作為討論某種程序設(shè)計(jì)語(yǔ)言語(yǔ)法的元語(yǔ)言<數(shù)字>::=0|1|2|……9::=“定義為”<字母>::=A|B|C|……Z|a|b|……z<標(biāo)識(shí)符>::=<字母>|<標(biāo)識(shí)符><字母>|<標(biāo)識(shí)符><數(shù)字>

….通過(guò)上述定義可知，所有以字母開(kāi)頭的，由字母和數(shù)字組成的字符串都是標(biāo)識(shí)符。BNF定義了一種語(yǔ)言，其中標(biāo)識(shí)符如上定義。BNF描述它所定義的語(yǔ)言，為元語(yǔ)言。60-BNF（巴科斯范式） BNF范式通常被作為討論某種程序設(shè)例如：漢語(yǔ)語(yǔ)法中定義了句子的結(jié)構(gòu)由主語(yǔ)、謂語(yǔ)、賓語(yǔ)組成。這里主謂賓只是描述了句子的結(jié)構(gòu)，并不是句子。而按照這種結(jié)構(gòu)組成的建立在漢字上的字符串就是句子。如他是學(xué)生。文法是一種元語(yǔ)言，一種方法，根據(jù)文法產(chǎn)生出語(yǔ)言的句子。61-例如：漢語(yǔ)語(yǔ)法中定義了句子的結(jié)構(gòu)由主語(yǔ)、謂語(yǔ)、賓語(yǔ)組成。這里三、Chomsky文法體系例如：BNF<標(biāo)識(shí)符>::=<字母><標(biāo)識(shí)符>::=<標(biāo)識(shí)符><字母><標(biāo)識(shí)符>::=<標(biāo)識(shí)符><數(shù)字><字母>::=a|b|……z|A|B|……|Z<數(shù)字>::=0|1|……9將::=改為→表示可被代替用I,L,D分別表示標(biāo)識(shí)符、字母、數(shù)字;62-三、Chomsky文法體系例如：62-三、Chomsky文法體系則上述表達(dá)式可以表示為 I→LI→ILI→IDL→a|b|….|zD→0|1|….9這就是一個(gè)文法的生成式集合。63-三、Chomsky文法體系則上述表達(dá)式可以表示為6三、Chomsky文法體系Chomsky文法體系中，任何一種文法必須包含有兩個(gè)不同的有限符號(hào)的集合，即非終結(jié)符集合N和終結(jié)符集合T。一個(gè)形式規(guī)則的有限集合P（生成式集合），一個(gè)起始符S。P中的生成式是用來(lái)產(chǎn)生語(yǔ)言句子的規(guī)則，而句子則是僅由終結(jié)符組成的字符串。這些字符串必須從一個(gè)起始符S開(kāi)始，不斷使用P中的生成式而推導(dǎo)出來(lái)?？梢?jiàn)文法的核心是生成式的集合，它決定了語(yǔ)言中句子的產(chǎn)生。64-三、Chomsky文法體系Chomsky文法體系中，任何一種文法的形式定義文法G是一個(gè)四元組G=(N，T，P，S)，其中

N非終結(jié)符的有限集合 T終結(jié)符的有限集合N∩T=Φ P形式為α→β的生成式的有限集合。 且α∈(N∪T)*N+(N∪T)*β∈(N∪T)* S起始符且S∈N。65-文法的形式定義文法G是一個(gè)四元組G=(N，T，P，S)，將上例用文法表示 G=(N，T，P，S)N={I,L,D}T={a,b,c,…z,0,1,…9}P={I,La,…,D0,…,D9}S={I}文法是語(yǔ)言的產(chǎn)生系統(tǒng)，研究怎樣構(gòu)造文法能產(chǎn)生出符合要求的句子。66-將上例用文法表示66-四．推導(dǎo)與句型1、直接推導(dǎo) 設(shè)G=（N,T,P,S）是文法，若A→β是P中的生成式，α和γ是（N∪T）*中的字符串，則有αAγ=>αβγ稱(chēng)αAγ直接推導(dǎo)出αβγ，或說(shuō)αβγ是αAγ的直接推導(dǎo)。67-四．推導(dǎo)與句型1、直接推導(dǎo)67-設(shè)G=(N,T,P,S)是文法，α、α0、α1…αn、α’都是（N∪T）*中的字符串，且α=α0、α’=αn，其中αi直接推導(dǎo)出αi+1（0≤i≤n）,則稱(chēng)序列α0=>α1=>α2=>…=>αn是長(zhǎng)度為n的推導(dǎo)序列，而α=α0是長(zhǎng)度為0的推導(dǎo)序列。對(duì)α推導(dǎo)出α’記為αα’，若推導(dǎo)序列長(zhǎng)度大于0，則記為αα’。推導(dǎo)序列的每一步，都產(chǎn)生一個(gè)字符串，這些字符串一般稱(chēng)為句型。2、推導(dǎo)序列68-設(shè)G=(N,T,P,S)是文法，α、α0、α1…αn、α3、句型和句子句型 字符串α是文法G的句型，當(dāng)且僅當(dāng)Sα，且α∈（N∪T）*。

句子ω是G的句子，當(dāng)且僅當(dāng)Sω,且ω∈T*。（ω是由終結(jié)符組成的字符串）例：I=>L=>a I=>IL=>LL=>zL=>zb句型包含句子69-3、句型和句子句型69-4．文法產(chǎn)生的語(yǔ)言由文法G產(chǎn)生的語(yǔ)言記為L(zhǎng)(G)。 L(G)={ω|ω∈T*且Sω}或： L(G)中的一個(gè)字符串，必是由終結(jié)符組成的，并且是從起始符S推導(dǎo)出來(lái)的。70-4．文法產(chǎn)生的語(yǔ)言70-第三節(jié)Chomsky文法體系分類(lèi)文法G=(N,T,P,S)；P:α→β

其中α∈（N∪T）*N+（N∪T）*β∈（N∪T）*屬于Chomsky文法體系該體系對(duì)生成式的形式做了一些規(guī)定，分為四類(lèi)，即0型、1型、2型、3型文法0型文法：無(wú)限制文法 對(duì)應(yīng)的語(yǔ)言：遞歸可枚舉語(yǔ)言，與圖靈機(jī)等價(jià)。71-第三節(jié)Chomsky文法體系分類(lèi)文法G=(N,T,P1型文法也稱(chēng)上下文有關(guān)文法（CSG：Context-sensitiveGrammar) 生成式的形式為α→β， 其中|α|≤|β|，β∈（N∪T）+， α∈（N∪T）*N+（N∪T）*對(duì)應(yīng)的語(yǔ)言：上下文有關(guān)語(yǔ)言（CSL：Context-sensitiveLanguage)若不考慮ε，與線性有界自動(dòng)機(jī)（LBA,LinearBoundedAutomaton）等價(jià)。72-1型文法也稱(chēng)上下文有關(guān)文法（CSG：Context-sens1型文法語(yǔ)言限定約束：左部的長(zhǎng)度小于右部不含A->ε上下文有關(guān)語(yǔ)言CSL是對(duì)實(shí)際程序語(yǔ)言結(jié)構(gòu)的抽象： 典型的這類(lèi)語(yǔ)言結(jié)構(gòu)包括：變量的聲明與引用、過(guò)程調(diào)用時(shí)形參與實(shí)參的一致性檢查等。73-1型文法語(yǔ)言限定約束：73-2型文法也稱(chēng)上下文無(wú)關(guān)文法（CFG：Context-freeGrammar) A→α, A∈N,且α∈（N∪T）*對(duì)應(yīng)的語(yǔ)言：上下文無(wú)關(guān)語(yǔ)言（CFL：Context-freeLanguage)。對(duì)應(yīng)的自動(dòng)機(jī)：下推自動(dòng)機(jī)（PDA：PushdownAutomaton)。74-2型文法也稱(chēng)上下文無(wú)關(guān)文法（CFG：Context-free語(yǔ)言限定約束：左部是1個(gè)非終結(jié)符。CFL對(duì)實(shí)際語(yǔ)言結(jié)構(gòu)的抽象：表示句子的語(yǔ)法結(jié)構(gòu)，如：表達(dá)式，嵌套結(jié)構(gòu){}。目前的程序設(shè)計(jì)語(yǔ)言主要采用CFL描述語(yǔ)法結(jié)構(gòu)。75-語(yǔ)言限定約束：75-3型文法也稱(chēng)正則文法右線性文法（Right-linearGrammar）：A→ωB或A→ω A、B∈N,ω∈T*。左線性文法（Left-linearGrammar）： A→Bω或A→ω A、B∈N,ω∈T*。對(duì)應(yīng)的語(yǔ)言：正則語(yǔ)言對(duì)應(yīng)的自動(dòng)機(jī)：有限自動(dòng)機(jī)（FiniteAutomaton）。76-3型文法也稱(chēng)正則文法76-文法舉例例1： G=({A,B,C},{a,b,d},P,A) P:A→AB；AB→CAAB；A→d；B→a；C→b是1型文法。A=>dA=>AB=>dB=>daA=>AB=>ABB=>dBB=>daB=>daaA=>AB=>CAAB=>bAAB=>bdAB=>bdCAAB=>bdbAAB=>bdbdAB=>bdbddB=>bdbdda77-文法舉例例1：77-文法舉例例2： G=({A,B,C},{a,b,c},P,A) P:A→abcA→aBbcBb→bBBc→CbccbC→CbaC→aaBaC→aa是1型文法。 其定義的L={anbncn|n≥1}A=>abcA=>aBbc=>abBc=>abCbcc=>aCbbcc=>aabbcc

78-文法舉例例2：78-文法舉例例3：

G=({S,B,C},{a,b},P,A) P:S→aC；S→bB；B→aS；B→bBBB→a； C→bS；C→aCC；C→b是2型文法

S=>aC=>abS=>aC=>aaCCS=>aC=>abS=>abaC=>ababS=>ababaC=>abababS=>bB=>bbBB=>bbaSB=>bbaaCB=>bbaabB=>bbaaba79-文法舉例例3：79-文法舉例例4： G=({A,B,C},{a,b,c},P,A)P:A→Ba；A→c；B→Cb；C→c左線性文法

L={c,cba}正則語(yǔ)言注意：已知語(yǔ)言求文法，文法不是唯一的，即可以有不同的表達(dá)方法。80-文法舉例例4：80-四類(lèi)文法之間的關(guān)系只是對(duì)生成式形式加以限制0型無(wú)限制1型不允許A→ε形式2型3型屬于2型不含A→ε的2型、3型屬于1型，1型、2型、3型均屬于0型。81-四類(lèi)文法之間的關(guān)系只是對(duì)生成式形式加以限制81-作業(yè)：P474,6,7題82-82-緒論課程信息為什么學(xué)習(xí)形式語(yǔ)言與自動(dòng)機(jī)形式語(yǔ)言與自動(dòng)機(jī)概述及應(yīng)用課程內(nèi)容及要求83-緒論課程信息1-

專(zhuān)業(yè)基礎(chǔ)課

上世紀(jì)60年代末、70年代初，研究的高峰

之后，向應(yīng)用領(lǐng)域滲透，研究生課程

近幾年，本科階段的專(zhuān)業(yè)基礎(chǔ)課

專(zhuān)業(yè)工作者必須的理論素養(yǎng)

計(jì)算模型計(jì)算機(jī)（不）能夠做什么問(wèn)題分類(lèi)計(jì)算的復(fù)雜性，算法分析形式系統(tǒng)建模工具（狀態(tài)機(jī)）抽象描述形式文法、形式表達(dá)式

課程性質(zhì)84-專(zhuān)業(yè)基礎(chǔ)課課程性質(zhì)2-相關(guān)課程先修課程

《離散數(shù)學(xué)》（《數(shù)理邏輯》，《集合論》）計(jì)算機(jī)導(dǎo)論與程序設(shè)計(jì)、數(shù)據(jù)結(jié)構(gòu)

后續(xù)課程

《編譯原理》

其它相關(guān)課程《模式識(shí)別》、《算法分析》85-相關(guān)課程先修課程3-教材： 形式語(yǔ)言與自動(dòng)機(jī) 王柏楊娟

編著 北京郵電大學(xué)出版社2003.186-教材：4-經(jīng)典參考書(shū)

書(shū)名

IntroductiontoAutomataTheory,Languages,andComputation（SecondEdition）

作者

JohnE.Hopcroft（Cornell）RajeevMotwani（Stanford）JeffereyD.Ullman（Stanford）

出版社

AddisonWesley（2001）

清華大學(xué)出版社（影印版）FirstEdition

中譯本《自動(dòng)機(jī)理論、語(yǔ)言和計(jì)算導(dǎo)引》徐美瑞等譯科學(xué)出版社，1990

John.E.Hopcroft,theTuringAwardwinnerin1986.87-經(jīng)典參考書(shū)書(shū)名Introductio其它參考書(shū)

《自動(dòng)機(jī)理論及其應(yīng)用》何成武科學(xué)出版社1990《形式語(yǔ)言及其句法分析》美A.V.阿霍等科學(xué)出版社1987《形式語(yǔ)言》王兵山，吳兵編國(guó)防工業(yè)大學(xué)出版社，1988

《形式語(yǔ)言與自動(dòng)機(jī)》陳有祺編著南開(kāi)大學(xué)出版社，天津，1999

88-其它參考書(shū)《自動(dòng)機(jī)理論及其應(yīng)用》6-2、為什么學(xué)習(xí)形式語(yǔ)言與自動(dòng)機(jī)形式語(yǔ)言與自動(dòng)機(jī)是計(jì)算機(jī)科學(xué)的基礎(chǔ)理論之一，是計(jì)算機(jī)學(xué)科的專(zhuān)業(yè)基礎(chǔ)課。在人工智能、電信領(lǐng)域等有廣泛的應(yīng)用。通過(guò)一些定理的證明和應(yīng)用，對(duì)大家進(jìn)行思維訓(xùn)練，從而為今后學(xué)習(xí)通信軟件，協(xié)議工程，編譯技術(shù)，人工智能等內(nèi)容提供理論基礎(chǔ)。89-2、為什么學(xué)習(xí)形式語(yǔ)言與自動(dòng)機(jī)形式語(yǔ)言與自動(dòng)機(jī)是計(jì)算機(jī)科學(xué)的2、為什么學(xué)習(xí)形式語(yǔ)言與自動(dòng)機(jī)對(duì)客觀世界的科學(xué)研究：目的在于把抽象數(shù)學(xué)的形式化體系發(fā)展成為與現(xiàn)實(shí)生活相似的理論模型，從而提供一種通用結(jié)構(gòu)來(lái)描述、理解和解決問(wèn)題。計(jì)算機(jī)科學(xué)：是關(guān)于計(jì)算知識(shí)的有系統(tǒng)的整體。90-2、為什么學(xué)習(xí)形式語(yǔ)言與自動(dòng)機(jī)對(duì)客觀世界的科學(xué)研究：目的在于2、為什么學(xué)習(xí)形式語(yǔ)言與自動(dòng)機(jī)計(jì)算機(jī)科學(xué)的兩個(gè)主要部分：構(gòu)成計(jì)算基礎(chǔ)的一些基本概念和模型；設(shè)計(jì)計(jì)算系統(tǒng)(軟件和硬件)的工程技術(shù)（設(shè)計(jì)理論的應(yīng)用）本課程著重介紹第一部分（涉及到一些第二部分的應(yīng)用），通過(guò)形式化技術(shù)對(duì)大家進(jìn)行思維訓(xùn)練，為今后的學(xué)習(xí)打好理論基礎(chǔ)。91-2、為什么學(xué)習(xí)形式語(yǔ)言與自動(dòng)機(jī)計(jì)算機(jī)科學(xué)的兩個(gè)主要部分：9-3、形式語(yǔ)言與自動(dòng)機(jī)概述及應(yīng)用本門(mén)課程將圍繞著什么是形式語(yǔ)言、什么是自動(dòng)機(jī)、以及形式語(yǔ)言和自動(dòng)機(jī)的相互關(guān)系進(jìn)行闡述。核心內(nèi)容

有限狀態(tài)自動(dòng)機(jī)，正規(guī)語(yǔ)言，正規(guī)表達(dá)式上下文無(wú)關(guān)文法，上下文無(wú)關(guān)語(yǔ)言，下推自動(dòng)機(jī)圖靈機(jī)，計(jì)算問(wèn)題分類(lèi)92-3、形式語(yǔ)言與自動(dòng)機(jī)概述及應(yīng)用本門(mén)課程將圍繞著什么是形式語(yǔ)言3.1

形式語(yǔ)言什么是形式語(yǔ)言形式語(yǔ)言:形式化描述的字母表上的字符串的集合。字母表：字符的有限集合。e.g.：26個(gè)英文字母構(gòu)成的字母表。字符串：字母表中的字符構(gòu)成的有限序列。e.g.hello,afjhkfyu

93-3.1形式語(yǔ)言什么是形式語(yǔ)言11-為什么用形式語(yǔ)言自然語(yǔ)言：人們平時(shí)說(shuō)話時(shí)所使用的一種語(yǔ)言，不同的國(guó)家和民族有著不同的語(yǔ)言。形式語(yǔ)言通過(guò)人們公認(rèn)的符號(hào)，表達(dá)方式所描述的一種語(yǔ)言，是一種通用語(yǔ)言，沒(méi)有國(guó)籍之分。形式語(yǔ)言是某個(gè)字母表上的字符串的集合，有一定的描述范圍。94-為什么用形式語(yǔ)言自然語(yǔ)言：人們平時(shí)說(shuō)話時(shí)所使用的一種語(yǔ)言，不為什么用形式語(yǔ)言例1：漢語(yǔ)：<主><謂><賓>――用數(shù)字、符號(hào)等形式化的東西來(lái)描述語(yǔ)言我吃飯――語(yǔ)法正確我飯吃――語(yǔ)法錯(cuò)誤飯吃我――語(yǔ)法正確，語(yǔ)義錯(cuò)誤95-為什么用形式語(yǔ)言例1：漢語(yǔ)：<主><謂><賓>為什么用形式語(yǔ)言例2：T為PASCAL語(yǔ)言所用的全部符號(hào)的集合。正確的PASCAL程序就是T上的語(yǔ)言。例3：在字母表T={a}上，L={a2n+1|n>=0}表示任意一對(duì)aa(包括0對(duì))后跟一個(gè)a的字符串。（即含有奇數(shù)個(gè)a的字符串。）96-為什么用形式語(yǔ)言例2：T為PASCAL語(yǔ)言所用的全部符號(hào)的集為什么用形式語(yǔ)言形式語(yǔ)言的最初起因：語(yǔ)言學(xué)家（Chomsky）想用一套形式化方法來(lái)描述語(yǔ)言。形式語(yǔ)言在自然語(yǔ)言研究中起步，在計(jì)算機(jī)科學(xué)中得到廣泛應(yīng)用。最初的應(yīng)用：編譯――讓計(jì)算機(jī)按照語(yǔ)法規(guī)則將高級(jí)語(yǔ)言方便地翻譯成機(jī)器語(yǔ)言。97-為什么用形式語(yǔ)言形式語(yǔ)言的最初起因：語(yǔ)言學(xué)家（Chomsk為什么用形式語(yǔ)言現(xiàn)在：已廣泛應(yīng)用在人工智能、圖象處理、通信協(xié)議、通信軟件等多個(gè)領(lǐng)域在計(jì)算機(jī)理論科學(xué)方面：是可計(jì)算理論（算法―在有限步驟內(nèi)求得解、算法復(fù)雜性、停機(jī)問(wèn)題、）、定理自動(dòng)證明、程序轉(zhuǎn)換（程序自動(dòng)生成）、模式識(shí)別等的基礎(chǔ)。98-為什么用形式語(yǔ)言現(xiàn)在：已廣泛應(yīng)用在人工智能、圖象處理、通信為什么用形式語(yǔ)言比爾.蓋茨：人類(lèi)計(jì)算的未來(lái)是讓計(jì)算機(jī)能夠看、聽(tīng)、學(xué)，能用自然語(yǔ)言與人類(lèi)交流形式化非常重要99-為什么用形式語(yǔ)言比爾.蓋茨：人類(lèi)計(jì)算的未來(lái)是讓計(jì)算機(jī)能夠看、

3.2.自動(dòng)機(jī)什么是自動(dòng)機(jī)？具有離散輸入輸出的數(shù)學(xué)模型。包括：輸入裝置 讀頭+輸入帶控制部件。

狀態(tài)轉(zhuǎn)移存儲(chǔ)單元大量通信軟件的基本工作機(jī)制都是有限狀態(tài)自動(dòng)機(jī)。自動(dòng)機(jī)理論在通信領(lǐng)域中的應(yīng)用極為廣泛。100-3.2.自動(dòng)機(jī)什么是自動(dòng)機(jī)？18-

3.2.自動(dòng)機(jī)自動(dòng)機(jī)接受一定的輸入，執(zhí)行一定的動(dòng)作，產(chǎn)生一定的結(jié)果。使用狀態(tài)遷移描述整個(gè)工作過(guò)程。狀態(tài)：一個(gè)標(biāo)識(shí)，能區(qū)分自動(dòng)機(jī)在不同時(shí)刻的狀況。有限狀態(tài)系統(tǒng)具有任意有限數(shù)目的內(nèi)部“狀態(tài)”自動(dòng)機(jī)的本質(zhì)：根據(jù)狀態(tài)、輸入和規(guī)則決定下一個(gè)狀態(tài)狀態(tài)＋輸入（激勵(lì)）＋規(guī)則―>狀態(tài)遷移101-3.2.自動(dòng)機(jī)自動(dòng)機(jī)接受一定的輸入，執(zhí)行一定的動(dòng)作，產(chǎn)生為什么叫自動(dòng)機(jī)？可能的狀態(tài)、運(yùn)行的規(guī)則都是事先確定的。一旦開(kāi)始運(yùn)行，就按照事先確定的規(guī)則工作，因此叫“自動(dòng)機(jī)”。有限自動(dòng)機(jī)可以認(rèn)為是由一個(gè)帶有讀頭的有限控制器和一條寫(xiě)有字符的輸入帶組成。102-為什么叫自動(dòng)機(jī)？可能的狀態(tài)、運(yùn)行的規(guī)則都是事先確定的。一旦開(kāi)自動(dòng)機(jī)舉例例1：打電話(自動(dòng)機(jī)在通信領(lǐng)域的應(yīng)用)。

在一次呼叫中，從建立連接到通話完畢，要經(jīng)歷摘機(jī)，撥號(hào)，應(yīng)答，進(jìn)行通話等過(guò)程，可以分別用四個(gè)狀態(tài)來(lái)表示。q0q1q2q3q4摘機(jī)收到撥號(hào)音撥號(hào)收應(yīng)答信號(hào)掛機(jī)收齊號(hào)碼q0:空閑狀態(tài)q1:等待撥號(hào)狀態(tài)q2:可以撥號(hào)狀態(tài)q3:等待應(yīng)答狀態(tài)q4:通話狀態(tài)103-自動(dòng)機(jī)舉例例1：打電話(自動(dòng)機(jī)在通信領(lǐng)域的應(yīng)用)。q0q1自動(dòng)機(jī)舉例例2：串口通信 兩臺(tái)微機(jī)通過(guò)串口通信,需在兩臺(tái)機(jī)器間建立好連接后，才可以傳遞數(shù)據(jù)，可以使用有限狀態(tài)自動(dòng)機(jī)，描述串口通信的狀態(tài)。傳輸數(shù)據(jù)收到應(yīng)答斷開(kāi)連接連接請(qǐng)求q0q1q2104-自動(dòng)機(jī)舉例例2：串口通信傳輸數(shù)據(jù)收到斷開(kāi)連接請(qǐng)求q0q1q2自動(dòng)機(jī)舉例例3。在許多數(shù)字電子技術(shù)基礎(chǔ)教科書(shū)中，串行序列檢測(cè)電路設(shè)計(jì)常常被作為同步時(shí)序電路設(shè)計(jì)的一個(gè)例題。要求設(shè)計(jì)“111”序列檢測(cè)電路。它要求電路有一個(gè)串行輸入端X及一個(gè)串行輸出端Z，當(dāng)輸入序列連續(xù)輸入3個(gè)1時(shí)，輸出為1，否則輸出為0。105-自動(dòng)機(jī)舉例例3。在許多數(shù)字電子技術(shù)基礎(chǔ)教科書(shū)中，串行序列檢測(cè)106-24-自動(dòng)機(jī)的分類(lèi)根據(jù)結(jié)構(gòu)不同，自動(dòng)機(jī)又可分為有限自動(dòng)機(jī)，下推自動(dòng)機(jī)，圖靈機(jī)等。下推自動(dòng)機(jī)可以看作是由一條輸入帶，一個(gè)有限控制器和一個(gè)下推棧組成?；緢D靈機(jī)由一個(gè)具有讀寫(xiě)頭的有限控制器和一條無(wú)限帶組成。使用自動(dòng)機(jī)，可以形式化的描述現(xiàn)實(shí)世界中的一些問(wèn)題。107-自動(dòng)機(jī)的分類(lèi)根據(jù)結(jié)構(gòu)不同，自動(dòng)機(jī)又可分為有限自動(dòng)機(jī)，下推自動(dòng)3.3形式語(yǔ)言與自動(dòng)機(jī)的關(guān)系形式語(yǔ)言和自動(dòng)機(jī)是密切相關(guān)的。形式語(yǔ)言――字符串自動(dòng)機(jī)――字符串的識(shí)別系統(tǒng)根據(jù)復(fù)雜程度可將形式語(yǔ)言分類(lèi)，根據(jù)自動(dòng)機(jī)的接受能力、處理能力的不同也將自動(dòng)機(jī)分類(lèi)。二者之間具有較好的對(duì)應(yīng)關(guān)系。108-3.3形式語(yǔ)言與自動(dòng)機(jī)的關(guān)系形式語(yǔ)言和自動(dòng)機(jī)是密切相關(guān)的。3.3形式語(yǔ)言與自動(dòng)機(jī)的關(guān)系109-3.3形式語(yǔ)言與自動(dòng)機(jī)的關(guān)系27-語(yǔ)言與有限自動(dòng)機(jī)（FiniteAutomata）設(shè)=0,1，L=ww中至少有一個(gè)0，如0011,10,110111

L,而11,,1111

L。下圖是一個(gè)可接受該語(yǔ)言的有限狀態(tài)自動(dòng)機(jī)110-語(yǔ)言與有限自動(dòng)機(jī)（FiniteAutomata）小結(jié)文法是定義語(yǔ)言的一個(gè)數(shù)學(xué)模型，而自動(dòng)機(jī)可看作是語(yǔ)言的識(shí)別系統(tǒng)。通過(guò)對(duì)一些定理的證明，說(shuō)明對(duì)于一個(gè)文法產(chǎn)生的語(yǔ)言，可以構(gòu)造相應(yīng)自動(dòng)機(jī)接受該語(yǔ)言：一個(gè)自動(dòng)機(jī)接受的語(yǔ)言，可以構(gòu)造對(duì)應(yīng)的文法產(chǎn)生該語(yǔ)言。一定類(lèi)型的自動(dòng)機(jī)和某種類(lèi)型的文法具有等價(jià)性。111-小結(jié)文法是定義語(yǔ)言的一個(gè)數(shù)學(xué)模型，而自動(dòng)機(jī)可看作是語(yǔ)言的識(shí)別課程內(nèi)容及要求課程內(nèi)容：書(shū)上二、三、四、五、六章。要求：通過(guò)本課學(xué)習(xí)，要求同學(xué)們掌握形式化描述方法，建立起形式語(yǔ)言與自動(dòng)機(jī)的概念，并能在實(shí)際中加以應(yīng)用。通過(guò)對(duì)定理的證明，對(duì)同學(xué)們進(jìn)行思維訓(xùn)練，并掌握一定的證明方法。112-課程內(nèi)容及要求課程內(nèi)容：書(shū)上二、三、四、五、六章。30-證明技術(shù)*定義、定理和證明基本證明方法歸納證明技術(shù)*

引自清華大學(xué)計(jì)算機(jī)系軟件技術(shù)研究所王生原老師課件113-證明技術(shù)*定義、定理和證明*引自清華大學(xué)計(jì)算機(jī)系軟定義、定理和證明定義：對(duì)象和概念的描述。定義需要精確，明確說(shuō)明對(duì)象的構(gòu)成。命題：描述某個(gè)對(duì)象所具有的某種性質(zhì)。也需精確。證明：邏輯論證，確認(rèn)一個(gè)命題為真。定理：被證明為真的（數(shù)學(xué)）命題。引理：被證明的命題，有助于證明另一個(gè)更有意義的命題114-定義、定理和證明定義：對(duì)象和概念的描述。定義需要精確，明確說(shuō)演繹證明

概念一個(gè)證明（proof）是命題的序列，其中的每一個(gè)命題或者是已知的命題，或者是由前面出現(xiàn)過(guò)的命題使用邏輯公理和規(guī)則得出.已知的命題集合稱(chēng)為假設(shè)（hypothesis）或前提（premise），最后一個(gè)命題稱(chēng)為該前提的結(jié)論（conclusion）.

115-演繹證明概念一個(gè)證明（proof）是命題的序“If–Then”命題

證明方法把If

部分作為已知的命題，把Then

部分作為結(jié)論.

舉例如果x+y=1，那么x2-y2=x-y.

證明:1x2-y2=(x+y)(x-y)//數(shù)學(xué)公理2(x+y)

=1//已知x2-y2=x-y//由1、2和算術(shù)性質(zhì)推出116-“If–Then”命題證明方法1x2-y2“If-And-Only-If”命題欲證AifandonlyifB，

可分別證明如下兩個(gè)命題：

1

ifAthenB，

2

ifBthenA.

117-“If-And-Only-If”命題欲證有關(guān)集合的命題在本課程中，經(jīng)常要證明兩種不同方法構(gòu)造的集合是相同的集合（比如語(yǔ)言表達(dá)的等價(jià)性）。設(shè)R,S為集合的表達(dá)式，下面兩個(gè)命題的證明需要參照集合的定義，分別表示為如下的命題。

欲證RS，可證明如下命題：

ifxRthenxS

欲證R=S，可分別證明如下兩個(gè)命題：

1

ifxRthenxS

2

ifxSthenxR118-有關(guān)集合的命題在本課程中，經(jīng)常要證明兩種不同方法構(gòu)造的集合原命題的逆否命題有時(shí)，證明原命題的逆否(contrapositive)命題更加方便.

欲證ifAthenB，

可證明如下命題：

ifnotBthennotA原因：兩個(gè)命題是等價(jià)，（蘊(yùn)涵邏輯等價(jià)）。119-原命題的逆否命題有時(shí)，證明原命題的逆否(contraposi反證法

反證（proofbycontradiction）

欲證ifHthenC，可以把H和notC都作為已知的命題，把任何一個(gè)矛盾(contradiction)命題作為新的結(jié)論.120-反證法反證（proofbycontradiction）舉例證明或否證

舉例證明存在量化的命題如命題：存在整數(shù)a，滿足a2=2a.

證明:取a=2.，滿足a2=2a.

舉反例否定全稱(chēng)量化的命題如命題：所有整數(shù)a，都滿足a2=2a.

否證:取a=1.，不滿足a2=2a.121-舉例證明或否證舉例證明存在量化的命題39-

歸納證明在處理遞歸定義的對(duì)象時(shí)“必不可少”。在自動(dòng)機(jī)理論中，需要?dú)w納證明處理遞歸定義的概念，比如：樹(shù)、表達(dá)式等。歸納法原理：如果證明了S(i),并且證明了對(duì)所有n≥i，S(n)蘊(yùn)涵S(n+1)，就可得出：對(duì)所有n≥i,S(n)成立。歸納證明與遞歸定義的對(duì)應(yīng)。歸納證明與結(jié)構(gòu)歸納法122-歸納證明在處理遞歸定義的對(duì)象時(shí)“必不可少”。在自動(dòng)機(jī)理論中歸納證明與結(jié)構(gòu)歸納法集合的遞歸定義由3部分構(gòu)成：

1基礎(chǔ)（basis）//直接定義集合中的元素（至少1個(gè)）

2歸納（induction）//從已知元素生成新元素的規(guī)則

3極小性限制//申明集合中的元素只能由1、2生成

123-歸納證明與結(jié)構(gòu)歸納法集合的遞歸定義41-歸納證明與結(jié)構(gòu)歸納法結(jié)構(gòu)歸納法對(duì)于歸納（遞歸）定義的集合S，欲證對(duì)于任意xS，滿足性質(zhì)P(x).

1基礎(chǔ)（basis）//若有直接定義aS，則證明P(a)

2歸納（induction）//若歸納定義中有規(guī)則

ifa1,a2,,anSthenf(a1,a2,,an)S，則證明

ifP(a1),P(a2),,P(an)SthenP(f(a1,a2,,an))124-歸納證明與結(jié)構(gòu)歸納法結(jié)構(gòu)歸納法42-

歸納定義合法括號(hào)串的集合S

1基礎(chǔ)空串S

2歸納若xS，則(x)S；

若x,yS，則xyS.

3極小性限制S中的元素只能由1、2生成(或：S是滿足1、2的最小集合)

命題：合法括號(hào)串集合S中每個(gè)括號(hào)串的“(”與“)”數(shù)目相等

證明:

1基礎(chǔ)空串的“(”與“)”數(shù)目相等，都為0；

2歸納設(shè)x,y的“(”與“)”數(shù)目相等，前者為m，后者為n；

(x)的“(”與“)”數(shù)目都為m+1；

xy的“(”與“)”數(shù)目都為m+n.歸納定義與結(jié)構(gòu)歸納證明（例）125-歸納定義合法括號(hào)串的集合S歸納定義與結(jié)構(gòu)歸納證明（例）4

自然數(shù)自然數(shù)集合N是滿足如下條件的最小集合：

(1)0

N;(2)若

nN,則n的后繼n+1N

數(shù)學(xué)歸納法欲證對(duì)任意自然數(shù)n，P(n)成立，(1)先證

P(0)成立;(2)再證若

P(n)成立,則P(n+1)成立

另一種形式

(1)先證P(0)成立;(2)再證若對(duì)任意k<n，P(k)成立,則P(n)成立

對(duì)任何良序集合，都可以有這兩種形式基于自然數(shù)的歸納—一般數(shù)學(xué)歸納法126-自然數(shù)自然數(shù)集合N是滿足如下條件的最小集合：基于自然第二章語(yǔ)言及文法主要內(nèi)容：定義形式語(yǔ)言的術(shù)語(yǔ)給出文法的定義和文法的分類(lèi)要求掌握：語(yǔ)言和文法的形式定義CHOMSKY文法體系的分類(lèi)。127-第二章語(yǔ)言及文法主要內(nèi)容：45-第一節(jié)語(yǔ)言的定義與運(yùn)算一、語(yǔ)言的一些術(shù)語(yǔ)：

字母表：字符的有限集合，記為T(mén)。字符串：由字母表T中的字符構(gòu)成的序列稱(chēng)字母表T上的字符串（句子）。常記為u,v,w,x,y,z；

常用a,b,c,d標(biāo)識(shí)單個(gè)字符。128-第一節(jié)語(yǔ)言的定義與運(yùn)算一、語(yǔ)言的一些術(shù)語(yǔ)：46-字母表（Alphabet）

概念

形式符號(hào)的集合

記號(hào)常用T、表示

舉例英文字母表a,b,…,z,A,B,…,Z

英文標(biāo)點(diǎn)符號(hào)表,;:.?!’‘“”()…漢字表…,自,…,動(dòng),…,機(jī),…

化學(xué)元素表H,He,Li,…,

T=a,n,y,任,意129-字母表（Alphabet）概念形式符號(hào)的集合4字符串（string）

概念字母表T上的一個(gè)字符串（簡(jiǎn)稱(chēng)串），或稱(chēng)為字（word），為T(mén)

中字符構(gòu)成的一個(gè)有限序列。

空串（emptystring）,用表示，不包含任何字符。

舉例設(shè)T=a,b，則

,

a,ba,bbaba等都是串

字符串w

的長(zhǎng)度，記為w，是包含在w中字符的個(gè)數(shù)

舉例=0，bbaba=5ai

表示含有i個(gè)a的字符串

130-字符串（string）概念字母表T上的一個(gè)

連接（concatenation）

設(shè)x,y為串,且xa1a2…am,yb1b2…bn,則x與y的連接

xya1a2…amb1b2…bn

連接運(yùn)算的性質(zhì)

(xy)z

x（yz

）

xxx

xyx+y

關(guān)于字符串的運(yùn)算131-連接（concatenation）關(guān)于字符串

其它如取頭字符，取尾部，子串匹配

等

設(shè)ω1,ω2,ω3是字母表T上的字符串，稱(chēng)：ω1是字符串ω1ω2的前綴，ω2是字符串ω1ω2的后綴，ω2是字符串ω1ω2ω3的子串?？沾侨魏巫址那熬Y，后綴及子串。

例：abc的前綴aababcε.后綴cbcabcε.子串a(chǎn)bcabbcabcε,

即一個(gè)字符串可以看作是多個(gè)字符串的連接。

關(guān)于字符串的運(yùn)算132-其它如取頭字符，取尾部，子串匹配等關(guān)于字字符串ω的逆用表示。是字符串ω的倒置。ω=b1b2……bn=bnbn-1……b2b1

空串ε的逆還是ε133-字符串ω的逆用表示。是字符串ω的倒置。51-字母表的冪運(yùn)算

冪運(yùn)算

Tn

用來(lái)表示該字母表長(zhǎng)度為n的所有串的集合。設(shè)T為字母表，n為任意自然數(shù)，定義（1）T0=（2）設(shè)x

Tn-1，a

T，則a

x

Tn（3）

Tn中的元素只能由（1）和（2）生成

閉包

T*=

T0T1T2…

閉包

T+=

T1T2T3…

T*=T+，T+=T*

134-字母表的冪運(yùn)算冪運(yùn)算Tn用來(lái)表示該字母表閉包的物理意義

T的星號(hào)閉包T*：字母表T上的所有字符串和空串的集合。

T的正閉包T+：字母表T上的所有字符串構(gòu)成的集合。 T*=T+∪{ε}舉例設(shè)T=0，1，則

T0=，T1=0，1，T2=00，01，10，11，…

T*=，0，1，00，01，10，11，…

T+=

0，1，00，01，10，11，…135-閉包的物理意義T的星號(hào)閉包T*：字母表T上的所有字符串語(yǔ)言（Languages）

概念設(shè)T為字母表，則任何集合LT*是字母表T上的一個(gè)語(yǔ)言（language）

舉例

英文單詞集…,Eng