形式語(yǔ)言與自動(dòng)機(jī)-緒論

12023/10/15CollegeofComputerScience&Technology,BUPTFormalLanguagesandAutomata

課程名稱形式語(yǔ)言與自動(dòng)機(jī)教師姓名楊娟 （計(jì)算機(jī)學(xué)院軟件工程中心）

電話62283778信箱

yangjuan@助教徐晨陽(yáng)彭爽

22023/10/15CollegeofComputerScience&Technology,BUPT緒論課程信息為什么學(xué)習(xí)形式語(yǔ)言與自動(dòng)機(jī)形式語(yǔ)言與自動(dòng)機(jī)概述及應(yīng)用課程內(nèi)容及要求32023/10/15CollegeofComputerScience&Technology,BUPT

專業(yè)基礎(chǔ)課

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

之后，向應(yīng)用領(lǐng)域滲透，研究生課程逐漸普及，本科階段的專業(yè)基礎(chǔ)課

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

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

）抽象描述形式文法、形式表達(dá)式

課程性質(zhì)42023/10/15CollegeofComputerScience&Technology,BUPT相關(guān)課程先修課程

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

后續(xù)課程

《編譯原理》

其它相關(guān)課程《模式識(shí)別》、《算法分析》

52023/10/15CollegeofComputerScience&Technology,BUPT教材： 形式語(yǔ)言與自動(dòng)機(jī) 王柏楊娟

編著 北京郵電大學(xué)出版社2003.162023/10/15CollegeofComputerScience&Technology,BUPT經(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.72023/10/15CollegeofComputerScience&Technology,BUPT其它參考書(shū)

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

《形式語(yǔ)言與自動(dòng)機(jī)理論》蔣宗禮，姜守旭.清華大學(xué)出版社，2003《形式語(yǔ)言與自動(dòng)機(jī)》陳有祺編著機(jī)械工業(yè)出版社，2008

82023/10/15CollegeofComputerScience&Technology,BUPT為什么學(xué)習(xí)形式語(yǔ)言與自動(dòng)機(jī)形式語(yǔ)言與自動(dòng)機(jī)是計(jì)算機(jī)科學(xué)的基礎(chǔ)理論之一，是計(jì)算機(jī)學(xué)科的專業(yè)基礎(chǔ)課。在人工智能、電信領(lǐng)域等有廣泛的應(yīng)用。通過(guò)一些定理的證明和應(yīng)用，對(duì)大家進(jìn)行思維訓(xùn)練，從而為今后學(xué)習(xí)通信軟件，協(xié)議工程，編譯技術(shù)，人工智能等內(nèi)容提供理論基礎(chǔ)。92023/10/15CollegeofComputerScience&Technology,BUPT對(duì)客觀世界的科學(xué)研究：目的在于把抽象數(shù)學(xué)的形式化體系發(fā)展成為與現(xiàn)實(shí)生活相似的理論模型，從而提供一種通用結(jié)構(gòu)來(lái)描述、理解和解決問(wèn)題。計(jì)算機(jī)科學(xué)：是關(guān)于計(jì)算知識(shí)的有系統(tǒng)的整體。102023/10/15CollegeofComputerScience&Technology,BUPT計(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ǔ)。4種基本的專業(yè)能力計(jì)算思維能力算法的設(shè)計(jì)與分析能力程序設(shè)計(jì)和實(shí)現(xiàn)能力計(jì)算機(jī)軟硬件系統(tǒng)的認(rèn)知、分析、設(shè)計(jì)與應(yīng)用能力計(jì)算思維能力邏輯思維能力和抽象思維能力構(gòu)造模型對(duì)問(wèn)題進(jìn)行形式化描述理解和處理形式模型112023/10/15122023/10/15CollegeofComputerScience&Technology,BUPT2023/10/1513能力培養(yǎng)學(xué)生的形式化描述和抽象思維能力。使學(xué)生了解和初步掌握“問(wèn)題、形式化描述、自動(dòng)化（計(jì)算機(jī)化）”這一最典型的計(jì)算機(jī)問(wèn)題求解思路。形式語(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)題分類142023/10/15CollegeofComputerScience&Technology,BUPT152023/10/15CollegeofComputerScience&Technology,BUPT1．形式語(yǔ)言什么是形式語(yǔ)言形式語(yǔ)言:形式化描述的字母表上的字符串的集合。字母表：字符的有限集合。e.g.：26個(gè)英文字母構(gòu)成的字母表。字符串：字母表中的字符構(gòu)成的有限序列。e.g.hello,afjhkfyu

162023/10/15CollegeofComputerScience&Technology,BUPT為什么用形式語(yǔ)言自然語(yǔ)言：人們平時(shí)說(shuō)話時(shí)所使用的一種語(yǔ)言，不同的國(guó)家和民族有著不同的語(yǔ)言。形式語(yǔ)言通過(guò)人們公認(rèn)的符號(hào)，表達(dá)方式所描述的一種語(yǔ)言，是一種通用語(yǔ)言，沒(méi)有國(guó)籍之分。形式語(yǔ)言是某個(gè)字母表上的字符串的集合，有一定的描述范圍。172023/10/15CollegeofComputerScience&Technology,BUPT例1：漢語(yǔ)：<主><謂><賓>――用數(shù)字、符號(hào)等形式化的東西來(lái)描述語(yǔ)言我吃飯――語(yǔ)法正確我飯吃――語(yǔ)法錯(cuò)誤飯吃我――語(yǔ)法正確，語(yǔ)義錯(cuò)誤182023/10/15CollegeofComputerScience&Technology,BUPT例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的字符串。）192023/10/15CollegeofComputerScience&Technology,BUPT形式語(yǔ)言的最初起因：語(yǔ)言學(xué)家（Chomsky）想用一套形式化方法來(lái)描述語(yǔ)言。形式語(yǔ)言在自然語(yǔ)言研究中起步，在計(jì)算機(jī)科學(xué)中得到廣泛應(yīng)用。最初的應(yīng)用：編譯――讓計(jì)算機(jī)按照語(yǔ)法規(guī)則將高級(jí)語(yǔ)言方便地翻譯成機(jī)器語(yǔ)言。202023/10/15CollegeofComputerScience&Technology,BUPT現(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ǔ)。212023/10/15CollegeofComputerScience&Technology,BUPT比爾.蓋茨：人類計(jì)算的未來(lái)是讓計(jì)算機(jī)能夠看、聽(tīng)、學(xué)，能用自然語(yǔ)言與人類交流形式化非常重要例1：微軟對(duì)聯(lián)軟件網(wǎng)址：

/

例2：圖靈測(cè)試222023/10/15CollegeofComputerScience&Technology,BUPT圖靈測(cè)試(1)問(wèn)：請(qǐng)給我寫(xiě)出有關(guān)“第四號(hào)橋”主題的十四行詩(shī)。答：不要問(wèn)我這道題，我從來(lái)不會(huì)寫(xiě)詩(shī)。問(wèn)：34957加70764等于多少？答：（停30秒后）105721問(wèn)：你會(huì)下國(guó)際象棋嗎？答：是的。問(wèn)：我在我的K1處有棋子K；你僅在K6處有棋子K，在R1處有棋子R?，F(xiàn)在輪到你走，你應(yīng)該下那步棋？答：（停15秒鐘后）棋子R走到R8處，將軍！232023/10/15CollegeofComputerScience&Technology,BUPT圖靈測(cè)試(2)問(wèn)：你會(huì)下國(guó)際象棋嗎？答：是的。問(wèn)：你會(huì)下國(guó)際象棋嗎？答：是的。問(wèn)：請(qǐng)?jiān)俅位卮?，你?huì)下國(guó)際象棋嗎？答：是的。242023/10/15CollegeofComputerScience&Technology,BUPT圖靈測(cè)試(3)問(wèn)：你會(huì)下國(guó)際象棋嗎？答：是的。問(wèn)：你會(huì)下國(guó)際象棋嗎？答：是的，我不是已經(jīng)說(shuō)過(guò)了嗎？問(wèn)：請(qǐng)?jiān)俅位卮?，你?huì)下國(guó)際象棋嗎？答：你煩不煩，干嘛老提同樣的問(wèn)題。25CollegeofComputerScience&Technology,BUPT在線圖靈測(cè)試網(wǎng)址Elbot/一個(gè)猜角色機(jī)器人（ACharacter-GuessingGame）/微軟小冰（聊天機(jī)器人，回歸微信以公眾號(hào)的形式出現(xiàn)）第三代人工智能小冰于2015.8.20正式亮相。整合微軟多項(xiàng)全球領(lǐng)先的人工智能圖像與語(yǔ)音識(shí)別技術(shù)，除了原有的長(zhǎng)程情感對(duì)話能力，還具備能看、能聽(tīng)和能說(shuō)的全新人工智能感官。262023/10/15CollegeofComputerScience&Technology,BUPT2.自動(dòng)機(jī)什么是自動(dòng)機(jī)？具有離散輸入輸出的數(shù)學(xué)模型。大量通信軟件的基本工作機(jī)制都是有限狀態(tài)自動(dòng)機(jī)。自動(dòng)機(jī)理論在通信領(lǐng)域中的應(yīng)用極為廣泛。272023/10/15CollegeofComputerScience&Technology,BUPT自動(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)遷移282023/10/15CollegeofComputerScience&Technology,BUPT為什么叫自動(dòng)機(jī)？可能的狀態(tài)、運(yùn)行的規(guī)則都是事先確定的。一旦開(kāi)始運(yùn)行，就按照事先確定的規(guī)則工作，因此叫“自動(dòng)機(jī)”。有限自動(dòng)機(jī)可以認(rèn)為是由一個(gè)帶有讀頭的有限控制器和一條寫(xiě)有字符的輸入帶組成。292023/10/15CollegeofComputerScience&Technology,BUPT例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)302023/10/15CollegeofComputerScience&Technology,BUPT例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)求q0q1q2312023/10/15CollegeofComputerScience&Technology,BUPT根據(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)題。322023/10/15CollegeofComputerScience&Technology,BUPT3．形式語(yǔ)言與自動(dòng)機(jī)的關(guān)系形式語(yǔ)言和自動(dòng)機(jī)是密切相關(guān)的。形式語(yǔ)言――字符串自動(dòng)機(jī)――字符串的識(shí)別系統(tǒng)根據(jù)復(fù)雜程度可將形式語(yǔ)言分類，根據(jù)自動(dòng)機(jī)的接受能力、處理能力的不同也將自動(dòng)機(jī)分類。二者之間具有較好的對(duì)應(yīng)關(guān)系。332023/10/15CollegeofComputerScience&Technology,BUPT342023/10/15CollegeofComputerScience&Technology,BUPT語(yǔ)言與有限自動(dòng)機(jī)（FiniteAutomata）設(shè)=0,1，L=w

w中至少有一個(gè)0，如0011,10,110111

L,而11,,1111

L。下圖是一個(gè)可接受該語(yǔ)言的有限狀態(tài)自動(dòng)機(jī)352023/10/15CollegeofComputerScience&Technology,BUPT小結(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ǔ)言。一定類型的自動(dòng)機(jī)和某種類型的文法具有等價(jià)性。362023/10/15CollegeofComputerScience&Technology,BUPT課程內(nèi)容及要求課程內(nèi)容：書(shū)上二、三、四、五章。要求：通過(guò)本課學(xué)習(xí)，要求同學(xué)們掌握形式化描述方法，建立起形式語(yǔ)言與自動(dòng)機(jī)的概念，并能在實(shí)際中加以應(yīng)用。通過(guò)對(duì)定理的證明，對(duì)同學(xué)們進(jìn)行思維訓(xùn)練，并掌握一定的證明方法。372023/10/15CollegeofComputerScience&Technology,BUPT證明技術(shù)*基本證明方法歸納證明技術(shù)*

引自清華大學(xué)計(jì)算機(jī)系軟件技術(shù)研究所王生原老師課件382023/10/15CollegeofComputerScience&Technology,BUPT演繹證明

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

392023/10/15CollegeofComputerScience&Technology,BUPT“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ì)推出402023/10/15CollegeofComputerScience&Technology,BUPT“If-And-Only-If”命題

欲證AifandonlyifB，

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

1

ifAthenB，

2

ifBthenA.

412023/10/15CollegeofComputerScience&Technology,BUPT有關(guān)集合的命題設(shè)R,S為集合.

欲證R

S，

可證明如下命題：

ifx

Rthenx

S

欲證R=S，

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

1

ifx

Rthenx

S

2

ifx

Sthenx

R422023/10/15CollegeofComputerScience&Technology,BUPT原命題的逆否命題有時(shí)，證明原命題的逆否(contrapositive)命題更加方便.

欲證ifAthenB，

可證明如下命題：

ifnotBthennotA432023/10/15CollegeofComputerScience&Technology,BUPT反證法

反證（proofbycontradiction）

欲證ifHthenC，可以把H和notC都作為已知的命題，把任何一個(gè)矛盾(contradiction)命題作為新的結(jié)論.442023/10/15CollegeofComputerScience&Technology,BUPT舉例證明或否證

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

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

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

否證:取a=1.，不滿足a2=2a.452023/10/15CollegeofComputerScience&Technology,BUPT

集合的歸納定義

由3部分構(gòu)成：

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

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

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

結(jié)構(gòu)歸納法對(duì)于歸納定義的集合S，欲證對(duì)于任意x

S，滿足性質(zhì)P(x).

1基礎(chǔ)（basis）//若有直接定義a

S，則證明P(a)

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

ifa1,a2,

,an

Sthenf(a1,a2,

,an)

S，則證明

ifP(a1),P(a2),

,P(an)

thenP(f(a1,a2,

,an))

歸納定義與結(jié)構(gòu)歸納法462023/10/15CollegeofComputerScience&Technology,BUPT

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

1基礎(chǔ)空串

S

2歸納若x

S，則(x)

S；

若x,y

S，則xy

S.

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

命題：合法括號(hào)