形式語(yǔ)言與自動(dòng)機(jī)課件全書(shū)教學(xué)教程電子教案幻燈片

12024/9/13

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

22024/9/13

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

專業(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ì)42024/9/13

相關(guān)課程先修課程

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

后續(xù)課程

《編譯原理》

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

52024/9/13

為什么學(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ǔ)。形式語(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)題分類62024/9/13

72024/9/13

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

82024/9/13

為什么用形式語(yǔ)言自然語(yǔ)言：人們平時(shí)說(shuō)話時(shí)所使用的一種語(yǔ)言，不同的國(guó)家和民族有著不同的語(yǔ)言。形式語(yǔ)言通過(guò)人們公認(rèn)的符號(hào)，表達(dá)方式所描述的一種語(yǔ)言，是一種通用語(yǔ)言，沒(méi)有國(guó)籍之分。形式語(yǔ)言是某個(gè)字母表上的字符串的集合，有一定的描述范圍。92024/9/13

例1：漢語(yǔ)：<主><謂><賓>――用數(shù)字、符號(hào)等形式化的東西來(lái)描述語(yǔ)言我吃飯――語(yǔ)法正確我飯吃――語(yǔ)法錯(cuò)誤飯吃我――語(yǔ)法正確，語(yǔ)義錯(cuò)誤102024/9/13

例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的字符串。）112024/9/13

形式語(yǔ)言的最初起因：語(yǔ)言學(xué)家（Chomsky）想用一套形式化方法來(lái)描述語(yǔ)言。形式語(yǔ)言在自然語(yǔ)言研究中起步，在計(jì)算機(jī)科學(xué)中得到廣泛應(yīng)用。最初的應(yīng)用：編譯――讓計(jì)算機(jī)按照語(yǔ)法規(guī)則將高級(jí)語(yǔ)言方便地翻譯成機(jī)器語(yǔ)言。122024/9/13

現(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ǔ)。132024/9/13

2.自動(dòng)機(jī)什么是自動(dòng)機(jī)？具有離散輸入輸出的數(shù)學(xué)模型。大量通信軟件的基本工作機(jī)制都是有限狀態(tài)自動(dòng)機(jī)。自動(dòng)機(jī)理論在通信領(lǐng)域中的應(yīng)用極為廣泛。142024/9/13

自動(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)遷移152024/9/13

為什么叫自動(dòng)機(jī)？可能的狀態(tài)、運(yùn)行的規(guī)則都是事先確定的。一旦開(kāi)始運(yùn)行，就按照事先確定的規(guī)則工作，因此叫“自動(dòng)機(jī)”。有限自動(dòng)機(jī)可以認(rèn)為是由一個(gè)帶有讀頭的有限控制器和一條寫(xiě)有字符的輸入帶組成。162024/9/13

例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)172024/9/13

例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)求q0q1q2182024/9/13

根據(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)題。192024/9/13

3．形式語(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)系。202024/9/13

212024/9/13

語(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ī)222024/9/13

小結(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à)性。232024/9/13

課程內(nèi)容及要求課程內(nèi)容：書(shū)上二、三、四、五章。要求：通過(guò)本課學(xué)習(xí)，要求同學(xué)們掌握形式化描述方法，建立起形式語(yǔ)言與自動(dòng)機(jī)的概念，并能在實(shí)際中加以應(yīng)用。通過(guò)對(duì)定理的證明，對(duì)同學(xué)們進(jìn)行思維訓(xùn)練，并掌握一定的證明方法。第二章語(yǔ)言及文法主要內(nèi)容：定義形式語(yǔ)言的術(shù)語(yǔ)給出文法的定義和文法的分類要求掌握：語(yǔ)言和文法的形式定義CHOMSKY文法體系的分類。242024/9/13

第一節(jié)語(yǔ)言的定義與運(yùn)算一、語(yǔ)言的一些術(shù)語(yǔ)：

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

常用a,b,c,d

標(biāo)識(shí)單個(gè)字符。252024/9/13

262024/9/13

字母表（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,…

272024/9/13

字符串（string）

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

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

空串（emptystring）,用

表示，不包含任何字符。舉例設(shè)T=a,b，則

,

a,ba,bbaba等都是串

字符串w

的長(zhǎng)度，記為

w

，是包含在w中字符的個(gè)數(shù)。

舉例

=0，

bbaba

=5

ai

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

282024/9/13

連接（concatenation）

設(shè)x,y為串,且x

a1a2…am,y

b1b2…bn,則x與y的連接

xy

a1a2…amb1b2…bn

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

(xy)z

x（yz

）

x

x

x

xy

x+y

關(guān)于字符串的運(yùn)算292024/9/13

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

等

設(shè)ω1,ω2,ω3是字母表T上的字符串，稱ω1是字符串ω1ω2的前綴，ω2是字符串ω1ω2的后綴，且ω2是字符串ω1ω2ω3的子串。空串是任何字符串的前綴，后綴及子串。

例：

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

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

關(guān)于字符串的運(yùn)算302024/9/13

字符串ω的逆用表示。是字符串ω的倒置。ω=b1b2……bn=bnbn-1……b2b1

空串ε的逆還是ε312024/9/13

字母表的冪運(yùn)算

冪運(yù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*

322024/9/13

閉包的物理意義

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，…

332024/9/13

語(yǔ)言（Languages）

概念設(shè)T為字母表，則任何集合L

T*是字母表T上的一個(gè)語(yǔ)言（language）

舉例

英文單詞集

…,English,…,words,…

C

語(yǔ)言程序集

…

字母表？漢語(yǔ)成語(yǔ)集

…,馬到成功,…

化學(xué)分子式集

…,H2O,…,NaCl,…

any,…

342024/9/13

語(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ǔ)，差。352024/9/13

語(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ǔ)言的積不可交換。362024/9/13

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

第二節(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ǔ)言。372024/9/13

元語(yǔ)言定義：描述語(yǔ)言的語(yǔ)言 例如：各種各樣的程序設(shè)計(jì)語(yǔ)言當(dāng)人們要解釋或討論程序設(shè)計(jì)語(yǔ)言本身時(shí)，又需要一種語(yǔ)言，被討論的語(yǔ)言叫做對(duì)象語(yǔ)言，即某種程序設(shè)計(jì)語(yǔ)言，討論對(duì)象語(yǔ)言的語(yǔ)言稱為元語(yǔ)言。382024/9/13

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ǔ)言。392024/9/13

例如：漢語(yǔ)語(yǔ)法中定義了句子的結(jié)構(gòu)由主語(yǔ)、謂語(yǔ)、賓語(yǔ)組成。這里主謂賓只是描述了句子的結(jié)構(gòu)，并不是句子。而按照這種結(jié)構(gòu)組成的建立在漢字上的字符串就是句子。如他是學(xué)生。文法是一種元語(yǔ)言，一種方法，根據(jù)文法產(chǎn)生出語(yǔ)言的句子。402024/9/13

三、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ù)字;412024/9/13

則上述表達(dá)式可以表示為

I→L

I→IL

I→ID

L→a|b|….|z

D→0|1|….9這就是一個(gè)文法的生成式集合。422024/9/13

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)生。432024/9/13

文法的形式定義文法G是一個(gè)四元組G=(N，T，P，S)，其中

N

非終結(jié)符的有限集合

T

終結(jié)符的有限集合N∩T=Φ

P形式為α→β的生成式的有限集合。 且α∈(N∪T)*N+(N∪T)*,β∈(N∪T)*

S

起始符且S∈N。442024/9/13

將上例用文法表示 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)生出符合要求的句子。452024/9/13

四．推導(dǎo)與句型1、直接推導(dǎo) 設(shè)G=（N,T,P,S）是文法，若A→β是P中的生成式，α和γ是（N∪T）*中的字符串，則有αAγ=>αβγ稱αAγ直接推導(dǎo)出αβγ，或說(shuō)αβγ是αAγ的直接推導(dǎo)。462024/9/13

2、推導(dǎo)序列設(shè)G=(N,T,P,S)是文法，α、α0、α1…αn、α’都是（N∪T）*中的字符串，且α=α0、α’=αn，其中αi直接推導(dǎo)出αi+1（0≤i≤n）,則稱序列α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è)字符串，這些字符串一般稱為句型。472024/9/13

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句型包含句子482024/9/13

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)的。492024/9/13

第三節(jié)Chomsky文法體系分類文法G=(N,T,P,S)；P:α→β

其中α∈（N∪T）*N+（N∪T）*β∈（N∪T）*屬于Chomsky文法體系該體系對(duì)生成式的形式做了一些規(guī)定，分為四類，即0型、1型、2型、3型文法0型文法：無(wú)限制文法 對(duì)應(yīng)的語(yǔ)言：遞歸可枚舉語(yǔ)言，與圖靈機(jī)等價(jià)。502024/9/13

1型文法也稱上下文有關(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à)。512024/9/13

2型文法也稱上下文無(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)。522024/9/13

3型文法也稱正則文法右線性文法（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）。532024/9/13

例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=>bdbdda542024/9/13

例2： G=({A,B,C},{a,b,c},P,A)

P:A→abc

A→aBbc

Bb→bB

Bc→Cbcc

bC→Cb

aC→aaB

aC→aa是1型文法。 其定義的L={anbncn|n≥1}

A=>abc

A=>aBbc=>abBc=>abCbcc=>aCbbcc=>aabbcc

=>aaBbbcc552024/9/13

例3：

G=({S,B,C},{a,b},P,A) P:S→aC,S→bB,B→aS,B→bBB,

B→a,

C→bS,C→aCC,C→b

是2型文法

S=>aC=>ab

S=>aC=>aaCCS=>aC=>abS=>abaC=>ababS=>ababaC=>abababS=>bB=>bbBB=>bbaSB=>bbaaCB=>bbaabB=>bbaaba562024/9/13

例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á)方法。572024/9/13

四類文法之間的關(guān)系只是對(duì)生成式形式加以限制0型無(wú)限制1型不允許A→ε形式2型3型屬于2型不含A→ε的2型、3型屬于1型，1型、2型、3型均屬于0型。582024/9/13

第三章有限自動(dòng)機(jī)與右線性文法本章主要內(nèi)容確定有限自動(dòng)機(jī)非確定有限自動(dòng)機(jī)確定與非確定有限自動(dòng)機(jī)的等價(jià)性右線性文法和有限自動(dòng)機(jī)的等價(jià)性右線性文法的性質(zhì)(泵浦定理)使用歸納法進(jìn)行證明的方法592024/9/13

第一節(jié)有限自動(dòng)機(jī)一、有限狀態(tài)系統(tǒng)的概念狀態(tài):狀態(tài)是可以將事物區(qū)分開(kāi)的一種標(biāo)識(shí)。具有離散狀態(tài)的系統(tǒng)：如數(shù)字電路(0,1)，十字路口的紅綠燈。離散狀態(tài)系統(tǒng)的狀態(tài)數(shù)是有限的。具有連續(xù)狀態(tài)的系統(tǒng)：比如水庫(kù)的水位，室內(nèi)溫度等可以連續(xù)變化，即有無(wú)窮個(gè)狀態(tài)。有限狀態(tài)系統(tǒng)必然是離散狀態(tài)系統(tǒng)（而且狀態(tài)數(shù)有限），因?yàn)橹挥杏邢迋€(gè)狀態(tài)。602024/9/13

實(shí)例

一個(gè)人帶著一頭狼，一頭羊，以及一棵青菜，處于河的左岸。有一條小船,每次只能攜帶人和其余的三者之一。人和他的伴隨品都希望渡到河的右岸，而每擺渡一次，人僅能帶其中之一。然而如果人留下狼和羊不論在左岸還是在右岸，狼肯定會(huì)吃掉羊。類似地，如果單獨(dú)留下羊和菜，羊也肯定會(huì)吃掉菜。如何才能既渡過(guò)河而羊和菜又不被吃掉呢?612024/9/13

622024/9/13

MG－WC（處于左岸的子集－處于右岸的子集）將過(guò)河問(wèn)題模型化：人(M)狼(W)羊(G)菜(C)二、有限自動(dòng)機(jī)的概念有限自動(dòng)機(jī)的概念具有離散輸入輸出系統(tǒng)的一種數(shù)學(xué)模型

(可以沒(méi)有輸出，比較特殊的也可以沒(méi)有輸入).有限的狀態(tài)狀態(tài)+輸入

狀態(tài)轉(zhuǎn)移每次轉(zhuǎn)換的后繼狀態(tài)都唯一

DFA每次轉(zhuǎn)換的后繼狀態(tài)不唯一

NFA632024/9/13

FA的模型 FA可以理解成一個(gè)控制器，它讀一條輸入帶上的字符。642024/9/13

101101有限控制器(1)

控制器包括有限狀態(tài)；(2)

從左到右依次讀取字符；(3)

狀態(tài)+激勵(lì)

狀態(tài)遷移

(根據(jù)當(dāng)前所處狀態(tài)和輸入字符進(jìn)行狀態(tài)轉(zhuǎn)移)652024/9/13

有限狀態(tài)集

有限輸入符號(hào)集

轉(zhuǎn)移函數(shù)

一個(gè)開(kāi)始狀態(tài)

一個(gè)終態(tài)集合有限自動(dòng)機(jī)的五要素q0q1q2q3三、DFA的形式定義定義:DFA是一個(gè)五元組M=(Q,T,δ,q0,F)Q:有限的狀態(tài)集合T:有限的輸入字母表δ:轉(zhuǎn)換函數(shù)(狀態(tài)轉(zhuǎn)移集合):Q×T

Qq0:初始狀態(tài)，q0QF:終止?fàn)顟B(tài)集,FQ

662024/9/13

轉(zhuǎn)移圖表示的DFA672024/9/13

Q={q0,q1,q2,q3}

T={0,1

}

(q0,0)=q2,(q0,1)=q1(q1,0)=q3,(q1,1)=q0(q2,0)=q0,(q2,1)=q3(q3,0)=q1,(q3,1)=q2

q0

F={q0,q3}q0q1q2q3682024/9/13

轉(zhuǎn)移表表示的DFA

q0q1q2

q301q2q1q3q0q0q3q1q2

Q={q0,q1,q2,q3}

T={0,1

}

(q0,0)=q2,(q0,1)=q1(q1,0)=q3,(q1,1)=q0(q2,0)=q0,(q2,1)=q3(q3,0)=q1,(q3,1)=q2

q0

F={q0,q3}四、擴(kuò)展轉(zhuǎn)移函數(shù)適合于輸入字符串δ’函數(shù)：接收一個(gè)字符串的狀態(tài)轉(zhuǎn)移函數(shù)。

:QT*Q

對(duì)任何qQ，定義：1.(q,)=q2.若ω是一個(gè)字符串,a是一個(gè)字符 定義:δ’(q,ωa)=δ(δ’(q,ω),a)

692024/9/13

擴(kuò)展轉(zhuǎn)移函數(shù)適合于輸入字符串702024/9/13

q0q1q2

q301q2q1q3q0q0q3q1q2舉例

(q0,

)

=q0(q0,0)

=(q0,0)

=q2(q0,00)

=(q2,0)

=q0(q0,001)

=(q0,1)

=q1(q0,0010)

=(q1,0)

=q3q0q1q2q3DFA接受的語(yǔ)言被DFA接收的字符串:輸入結(jié)束后使DFA的狀態(tài)到達(dá)終止?fàn)顟B(tài)。否則該字符串不能被DFA接收.DFA接收的語(yǔ)言:被DFA接收的字符串的集合. L(M)=

w

(q0,w)F

例：T={0，1}712024/9/13

接收含有奇數(shù)個(gè)0的任意串五、格局為描述有限自動(dòng)機(jī)的工作過(guò)程，對(duì)于它在某一時(shí)刻的工作狀態(tài)，可用兩個(gè)信息表明：當(dāng)前狀態(tài)q，待輸入字符串w。兩者構(gòu)成一個(gè)瞬時(shí)描述，用（q,w）表示，稱為格局。初始格局：（q0,w)終止格局：(q,ε),q

F722024/9/13

如圖，接受001010的格局（q0,001010）┝(q2,01010)┝(q0,1010)┝(q1,010)┝(q3,10)┝(q2,0)┝(q0,ε)格局?jǐn)?shù)量是無(wú)限的。有限狀態(tài)自動(dòng)機(jī)是無(wú)記憶的。例如接受0010101111和接受01011111時(shí)，都可以進(jìn)入格局(q0,1111)。732024/9/13

格局示例q0q1q2q3如果對(duì)某個(gè)q

F,有(q0,w)

┝(q,

),則稱輸入字符串w是可被確定的有限自動(dòng)機(jī)接受的。742024/9/13

設(shè)計(jì)有限自動(dòng)機(jī)自動(dòng)機(jī)的設(shè)計(jì)是一個(gè)創(chuàng)造過(guò)程，沒(méi)有簡(jiǎn)單的算法或過(guò)程。技巧：假設(shè)自己是機(jī)器，思考如何去實(shí)現(xiàn)機(jī)器的任務(wù)。為判斷到目前為止所看到的字符串是否滿足某個(gè)語(yǔ)言，須估算出讀一個(gè)字符串時(shí)需要記住哪些關(guān)鍵的東西。

例：構(gòu)造自動(dòng)機(jī)，識(shí)別所有由奇數(shù)個(gè)a和奇數(shù)個(gè)b組成的字符串。關(guān)鍵：不需要記住所看到的整個(gè)字符串，只需記住至此所看到的a、b個(gè)數(shù)是偶數(shù)還是奇數(shù)。

752024/9/13

q偶a偶bq奇a偶bq偶a奇bq奇a奇bStartbaabaabb第二節(jié) 不確定的有限自動(dòng)機(jī)(NFA) 修改DFA的模型，使之在某個(gè)狀態(tài)，對(duì)應(yīng)一個(gè)輸入，可以有多個(gè)轉(zhuǎn)移，到達(dá)不同的狀態(tài)，則稱為不確定的有限自動(dòng)機(jī)。

例：762024/9/13

(1)(2)一、不確定有限自動(dòng)機(jī)的形式定義NFA是一個(gè)五元組，M=(Q,T,δ,q0,F)。

其中δ是Q×T->2Q的函數(shù)，其余與DFA相同。如果接收一個(gè)字符串后NFA進(jìn)入一個(gè)狀態(tài)集，而此集合中包含一個(gè)以上F中的狀態(tài)，

則稱NFA接收該字符串。772024/9/13

782024/9/13

(1)(2)pq

r0{q}

{q}

{q,r}

1pq

r0{p}{r}

{r}

1{p,q}轉(zhuǎn)移圖和轉(zhuǎn)移表表示的NFA格局示例如圖所示，用格局序列描述自動(dòng)機(jī)的工作過(guò)程，當(dāng)輸入字符串是011011時(shí)，則有792024/9/13

二、NFA的狀態(tài)轉(zhuǎn)移函數(shù)與DFA唯一不同之處:Q

2Q同樣，

δ可擴(kuò)展為δ’

(

:QT*2Q)1.δ’(q,ε)

=

{q}

含義：

不允許無(wú)輸入的狀態(tài)變化。2.δ'(q,ωa)={p|存在r∈δ'(q,ω)∧p∈δ(r,a)}含義:δ’(q,ωa)對(duì)應(yīng)的狀態(tài)集合是δ’(q,ω)對(duì)應(yīng)的每個(gè)狀態(tài)下再接收字符a以后可能到達(dá)的狀態(tài)集合的并集.

即若(q

,ω)={r

1,r

2,,r

k},則

(q

,ωa)=(r

i,a)其中ω

T*,a

T，r

i

Q802024/9/13

812024/9/13

舉例

(p

,

)

={p}

(p

,0)

={q}

(p

,01)

={q,r}

(p

,010)

={q}

(p

,0100)

={q}

(p

,01001)={q,r}

pq

r0{q}

{q}

{q,r}

1擴(kuò)展轉(zhuǎn)移函數(shù)適合于輸入字符串822024/9/13

NFA

接受的語(yǔ)言

設(shè)一個(gè)NFAA=(Q,

T,

,q0,F)

定義A的語(yǔ)言:

L(A)=

w

(q0,w)

F

第三節(jié)

NFA與DFA的等價(jià)性DFA是NFA的特例，所以NFA必然能接收DFA能接收的語(yǔ)言。

因此證明等價(jià)性只要能夠證明一個(gè)NFA所能接收的語(yǔ)言必能被另一個(gè)DFA所接收。1.定理：設(shè)一個(gè)NFA接受語(yǔ)言L，那么必然存在一個(gè)DFA接受L。2.

證明:策略：對(duì)于任意一個(gè)NFA，構(gòu)造一個(gè)接收它所能接收語(yǔ)言的DFA，這個(gè)DFA的狀態(tài)對(duì)應(yīng)了NFA的狀態(tài)集合。832024/9/13

842024/9/13

從NFA構(gòu)造等價(jià)的DFA(子集構(gòu)造法)設(shè)L是某個(gè)NFAMN=(QN,

T,

N,q0,FN)的語(yǔ)言,則存在一個(gè)DFAMD,滿足L(MD)=L(MN)=L.

證明:定義

MD=(QD,

T,

D,{q0},FD

),

其中

QD

=

S

S

QN

=2Q

對(duì)S

QD

和aT

,

D(S,a)=

N(q,a)，

FD=

S

S

QN

S

FN

需要證明:對(duì)任何w

T*

,

D({q0}

,w)=

N(q0,w).

歸納于|w|可證上述命題.

q

S852024/9/13

pq

r0{q}

{q}

{q,r}

10

{q}1

{p}{q}

{r}{p,q}

{p,r

}

{q,r

}

{p,q,r

}

{q}{q,r}

{q}{q,r}{q}

{q}{q,r}{q}{q,r}

子集構(gòu)造法舉例862024/9/13

pq

r0{p}{r}

{r}

1{p,q}01{p}

{p,q,r}{p}{p,q}{p}{p,q}{p,q}{p,r}{p,q,r}

{p,r}{p,r}{p,q,r}子集構(gòu)造法舉例872024/9/13

證明:從NFA構(gòu)造等價(jià)的DFA設(shè)MN=(QN,

T,

N,q0,FN)是一個(gè)NFA

,通過(guò)子集構(gòu)造法

得到相應(yīng)的DFAMD=(QD,

T,

D,{q0},FD

),則對(duì)任何w

T*

,

D({q0}

,w)=

N(q0,w).

證明:歸納于|w|1設(shè)|w|=0,即

w=

.由定義知

D({q0}

,

)=

N(q0,

)={q0}

.2

設(shè)|w|=n+1,并

w=xa,a

T.注意到|x|=n.假設(shè)

D({q0}

,x)=

N(q0,x)={p1,p2,

,pk

}.則

D({q0}

,w)=

D(

D({q0}

,x),a)=

D({p1,p2,

,pk

},a)=

N(pi,a).=

N(q0,w)i=1k882024/9/13

實(shí)踐中,通過(guò)子集構(gòu)造法得到的DFA的狀態(tài)數(shù)目與原NFA的狀態(tài)數(shù)目大體相當(dāng).

在較壞的情況下,上述DFA的狀態(tài)數(shù)目接近于所有子集的數(shù)目.

舉例由如下NFA構(gòu)造的DFA的狀態(tài)數(shù)目至少為2n子集構(gòu)造法得到的狀態(tài)數(shù)q0q1q2qn第四節(jié) 有

轉(zhuǎn)換的NFA一、定義 概念：當(dāng)輸入空串ε(無(wú)輸入)時(shí)，也能引起狀態(tài)的轉(zhuǎn)移。例：892024/9/13

輸入“002”時(shí)的轉(zhuǎn)移格局：

q0q1q2012εε902024/9/13

-NFA的形式定義一個(gè)

-NFA

是一個(gè)五元組A=(Q,

T,

,q0,F).有限狀態(tài)集

有限輸入符號(hào)集

轉(zhuǎn)移函數(shù)

一個(gè)開(kāi)始狀態(tài)

一個(gè)終態(tài)集合q0

Q

F

Q與NFA的不同之處:Q(T

)

2Q912024/9/13

-NFA如何接受輸入符號(hào)串q1q0q2q3q5

,+,–q4

該

-NFA可以接受的字符串如：

3.14

+.314

–314.922024/9/13

二、

-閉包（closure）概念

狀態(tài)q的

-閉包，記為

-

CLOSURE或ECLOSE

，定義為從q經(jīng)所有的

路徑可以到達(dá)的狀態(tài)（包括q自身），如：

q0q1q2012εε

-CLOSURE

(q0)={q0,q1,q2}

-CLOSURE

(q1)={q1,q2}

-CLOSURE

(q2)=

{q2

}狀態(tài)子集I的ε-閉包： ε-CLOSURE(I)＝

∪

ε-CLOSURE(q)q∈I例： ε-CLOSURE({q1，q2})＝ε-CLOSURE(q1)∪ε-CLOSURE(q2)＝{q1，q2}Ia概念：對(duì)于狀態(tài)子集I

Q，任意a∈T，定義Ia如下：

Ia=ε-Closure(P) 其中P=δ（I，a）.即P是從I中的狀態(tài)經(jīng)過(guò)一條標(biāo)a的邊可以到達(dá)的狀態(tài)集合932024/9/13

942024/9/13

例：I＝{q0，q1}，求I1I1＝ε-CLOSURE（δ（I，1））＝ε-CLOSURE（δ（{q0，q1}，1））＝ε-CLOSURE（Φ∪{q1}）＝{q1，q2}q0q1q2012εε952024/9/13

擴(kuò)展轉(zhuǎn)移函數(shù)適合于輸入字符串設(shè)一個(gè)

-NFA,

:Q

T

2Q

擴(kuò)充定義:QT*2Q

對(duì)任何qQ，定義：1(q,)=ECLOSE(q)2δ'(q，ωa)＝ε-CLOSURE(P)其中P＝{p|存在r∈δ'(q，ω)∧p∈δ(r，a)}注意：此時(shí)δ(q，a)δ'(q，a)，因?yàn)棣?q，a)表示由q出發(fā)，只沿著標(biāo)a的路徑所能到達(dá)的狀態(tài)，而δ'(q，a)表示由q出發(fā)，沿著標(biāo)a(包括ε轉(zhuǎn)換在內(nèi))的路徑所能到達(dá)的狀態(tài).962024/9/13

ε-NFA中，δ與δ’函數(shù)的不同

舉例計(jì)算(q0,a)

δ'(q0，ε)＝ε-CLOSURE(q0)＝{q0，q2}δ'(q0，a)＝ε-CLOSURE(δ(δ'(q0，ε)，a))＝ε-CLOSURE(δ({q0，q2}，a))＝ε-CLOSURE(δ(q0，a)∪δ(q2，a))＝ε-CLOSURE({q1}∪{q3})＝{q1，q2}∪{q3}＝{q1，q2，q3}同理：δ'(q0，aa)＝{q3}ε-CLOSURE(q0)＝{q0，q2}ε-CLOSURE(q1)＝{q1，q2}ε-CLOSURE(q2)＝{q2}ε-CLOSURE(q3)＝{q3}972024/9/13

三、-NFA

的

語(yǔ)言

設(shè)一個(gè)

-NFAM=(Q,

T,

,q0,F)

定義M

的語(yǔ)言：

L(M)=

ω|(q0

,ω)

F

即

滿足δ'(q0，ω)含有F的一個(gè)狀態(tài)

四、有

轉(zhuǎn)換的NFA與無(wú)

轉(zhuǎn)換的NFA的等價(jià)1.

-NFA<==>NFA

具有

轉(zhuǎn)移的NFA是不具

轉(zhuǎn)移的NFA的一般情況，所以只要證明下面的定理即可：定理：如果L被一個(gè)具有

轉(zhuǎn)移的NFA接收，

那么L可被一個(gè)不具

轉(zhuǎn)移的NFA接收。證明思路：構(gòu)造一個(gè)不具

轉(zhuǎn)移的NFA，證明其接收具有

轉(zhuǎn)移的NFA所接受的語(yǔ)言。982024/9/13

992024/9/13

從

-NFA構(gòu)造等價(jià)的無(wú)

NFA設(shè)M=(Q,T,

,q0,F)是一個(gè)

-NFA，可構(gòu)造一個(gè)無(wú)

的NFAM1=(Q,T,

1

,q0,F1)，

對(duì)任何aT,

1(q,a)=

(q

,a)。

（注意δ與δ’的區(qū)別與聯(lián)系。而δ1和δ’是相等的。）F1

＝F∪{q0}若ε-CLOSURE(q0)

F

F否則{1002024/9/13

從

-NFA構(gòu)造等價(jià)的無(wú)

NFA證明:采用歸納法證明δ1（q0，ω）＝δ’（q0，

ω），|ω|>=1。當(dāng)|w|=0,即w=

時(shí)，不一定相等.∵δ1(q0，ε)＝{q0}，

而δ’(q0，ε)＝ε-CLOSURE(q0) 因此，從|ω|＝1開(kāi)始證明當(dāng)|ω|=1時(shí)，定義相等。 由δ1定義δ1（q0，a）＝δ’（q0，a）設(shè)當(dāng)|ω|<=n時(shí)，δ1（q0,ω）=δ’（q0,ω），則當(dāng)|ωa|=n+1時(shí)，左側(cè)＝δ1（q0,ωa）

＝δ1(δ1（q0，ω），a) ＝δ1(δ’（q0，ω），a)由歸納假設(shè) ＝δ1(R，a)設(shè)R＝δ’（q0，ω） ＝∪δ1(q，a)q∈R ＝∪δ’(q，a)q∈R.由δ1定義 ＝δ’(R，a)＝δ’(δ’（q0，ω），a)∵R＝δ’（q0，ω） ＝δ’(q0，ωa) ＝右側(cè)再證:δ1（q0，ω）含F(xiàn)1的一個(gè)狀態(tài)當(dāng)且僅當(dāng)δ’（q0，ω）含F(xiàn)的一個(gè)狀態(tài)（略）1012024/9/13

證明同時(shí)展示了一種將

-NFA轉(zhuǎn)化為NFA的方法.

-NFA

<==>

NFA

<==>

DFA例：將

-NFA轉(zhuǎn)換為NFA.（圖3.4.1，3.4.3）1022024/9/13

q0q1q2012εεq0q1q20120,11,20,1,21032024/9/13

舉例q1q0q2q3q5

,+,–q4{q0}{q1}{q1q4}{q2}{q2q3q5}{q3q5}1042024/9/13

第五節(jié)

正則集和正則式正則集：字母表上一些特殊形式的字符串的集合，是正則式所表示的集合。

正則式：用類似代數(shù)表達(dá)式的方法表示正則語(yǔ)言。運(yùn)算:作用于語(yǔ)言上的三種代數(shù)運(yùn)算

聯(lián)合（union）

連接（concatenation）（星）閉包（closure）

1052024/9/13

正則表達(dá)式（regularexpression）歸納定義正則表達(dá)式如下：基礎(chǔ)：ε，

，a（a∈T）都是正則式(原子正則式)， 相應(yīng)的正則集為{ε}，

，{a}歸納：如果A和B是正則式，且分別代表集合L(A)和L(B)，則(A+B)，(A.B)，A*也是正則式，分別表示以下正則集：L(A)∪L(B)(語(yǔ)言A/語(yǔ)言B的串)L(A).L(B) (兩個(gè)語(yǔ)言中的串的連接)L(A)* (語(yǔ)言A中的串的多次連接)僅通過(guò)有限次使用以上兩步定義的表達(dá)式，才是字母表T上的正則式。這些正則式所表示的字符串集合是T上的正則集。

1062024/9/13

正則表達(dá)式算符優(yōu)先級(jí)算符優(yōu)先級(jí)（precedence）依次為

（closure）

?連接（concatenation）

（union）定義：若兩個(gè)正則式表示相同的正則集，則稱這兩個(gè)正則式相等。即R1＝R2<==>L(R1)=L(R2)注1：正則集是T*的子集。注2：L+包含ε當(dāng)且僅當(dāng)L包含ε。注3：每個(gè)正則集至少對(duì)應(yīng)一個(gè)正則式（可有無(wú)窮多個(gè)正則式）1072024/9/13

正則表達(dá)式舉例書(shū)p55例1表示如下語(yǔ)言的正則表達(dá)式：語(yǔ)言中的每個(gè)字符串由交替的0

s和1

s

構(gòu)成

(01)*+(10)*+0(10)*+1(01)*

(+1)(01)*(+0)

(+0)(10)*(+1)1082024/9/13

語(yǔ)言的聯(lián)合（union）運(yùn)算兩個(gè)語(yǔ)言L和M的聯(lián)合

L

M=

w

w

L

w

M

舉例設(shè)L=

001,10,111

,

M=

,001

,則

L

M=

,10,001,111

1092024/9/13

語(yǔ)言的連接（concatenation）運(yùn)算

兩個(gè)語(yǔ)言L和M的連接

L·

M=

w1w2

w1

L

w2

M

有時(shí)記L·

M為L(zhǎng)M

舉例設(shè)L=

001,10,111

,

M=

,001

,則

LM=

001,10,111,001001,10001,111001

1102024/9/13

語(yǔ)言的閉包（closure）運(yùn)算語(yǔ)言L的閉包

L*=

wn

w

L

n0

,其中wn為w

的n次連接或L*=L0

L1

L2

…=

i0

Li,其中

L0=

，L1=L,L2=LL,…

舉例設(shè)L=

0,11

,

則

L*=

,

0,11,00,011,110,1111,000,0011,0110,01111,1100,11011,11110,111111,…

1112024/9/13

正則式的性質(zhì)交換律（commutativity）和結(jié)合律（associativeity）(1)(α+β)+γ＝α+(β+γ)(2)(αβ)γ＝α(βγ)(3)α+β＝β+α等冪律（idempotentlaw）(4)α+α＝α分配律（distributivelaw）(5)α(β+γ)＝αβ+αγ(6)(β+γ)α＝βα+γα1122024/9/13

正則式的性質(zhì)幺元（identities）和零元（annihilators）(7)α+φ＝φ+α＝α(8)αφ＝φα＝φ(9)αε＝εα＝α

與閉包相關(guān)的定律(10)(α*)*＝α*(11)α*＝α+α*

*=

*=

L+=LL*=L*L（L+的定義）L*=L++

1132024/9/13

正則式的性質(zhì)(11)α*＝α+α*

證明：∵α*＝ε＋α＋α2＋…＋αn

L(α*)＝{ε}∪L(α)∪L(α2)∪…∪L(αn)L(α+α*)＝L(α)∪({ε}∪L(α)∪L(α2) ∪…∪L(αn))＝L(α)∪L(α*)而L(α)L(α*)∴α+α*＝α*1142024/9/13

右線性文法與正則式

右(左)線性文法又稱為正則文法，右線性文法與正則式可以用來(lái)代表同一正則語(yǔ)言。二者具有等效性。

例：文法S

aS，S

a 對(duì)應(yīng)正則式：a+，或者a*a1152024/9/13

從右線性文法導(dǎo)出正則式求解規(guī)則:設(shè)x

=αx+β，α∈T*，β∈(N∪T)*,x∈N則x的解為x＝α*β證明：x

=αx+β表示x有兩個(gè)生成式：x

αx

和x

β，生成的語(yǔ)言為（β，αβ，ααβ，αααβ,…），顯然該語(yǔ)言可用正則式α*β表示。

1162024/9/13

舉例（P56例2）設(shè)右線性文法G=({S,A,B},{a,b},P,S}，生成式P如下：S→aA,S→bB,S→b,A→bA,A→,B→bS以上生成式寫(xiě)成聯(lián)立方程為 S=aA+bB+b（1） A=bA+（2） B=bS（3）對(duì)式（2）利用規(guī)則R和性質(zhì)α=α得

A=b*4）將式（4）和式（3）代入式（1）中的A、B，得 S=ab*+bbS+b=bbS+ab*+b=(bb)*(ab*+b)所以由G產(chǎn)生的語(yǔ)言用正則式表示為(bb)*(ab*+b)

1172024/9/13

第六節(jié)正則集和右線性文法正則集是由右線性文法產(chǎn)生的語(yǔ)言由右線性文法產(chǎn)生的語(yǔ)言都是正則集(一).求證正則集是由右線性文法產(chǎn)生的語(yǔ)言證明方法：

找出相應(yīng)的右線性文法，使之產(chǎn)生的語(yǔ)言是這些正則集。1182024/9/13

首先從最簡(jiǎn)單的正則式出發(fā)，求證其正則集Φ，{ε}，{a}是右線性語(yǔ)言。證明：對(duì)正則集Φ，有右線性文法G＝{{S}，T，Φ，S}，使L(G)=Φ對(duì)正則集{ε},有右線性文法G＝{{S}，T，{S->ε}，S}，使L(G)={ε}對(duì)正則集{a}，有右線性文法G＝{{S}，T，{S->a}，S}，使L(G)={a}

1192024/9/13

將對(duì)由并，積，閉包形成的正則集的證明，改為對(duì)右線性語(yǔ)言的證明。 設(shè)在字母表T上，有語(yǔ)言L1和L2，則L1∪L2，L1.L2，L1*都是右線性語(yǔ)言。證明方法：分別找出相應(yīng)的右線性文法。設(shè)G1＝（N1，T，P1，S1）產(chǎn)生L1G2＝（N2，T，P2，S2）產(chǎn)生L2N1N2＝Φ(若不為空,則可對(duì)N中符號(hào)換名)1202024/9/13

構(gòu)造G＝（N，T，P，S）產(chǎn)生L，使L=L1∪L2其中 N＝N1∪N2∪{S},S為新的非終結(jié)符；

P＝P1∪P2∪{S－>S1，S－>S2}先證LL1∪L2：在G中，由G的定義，對(duì)于任意ω，意味著或者（按G1的產(chǎn)生式），或者（按G2的產(chǎn)生式）即文法G的每個(gè)句子或由G1產(chǎn)生，或由G2產(chǎn)生?！郘(G)L(G1)∪L(G2)再證L1∪L2L：設(shè)有ω∈L1∪L2，則存在推導(dǎo)S1

G1＝>+ω或S2

G2＝>+ω∴必有SG＝>+ω。即L1∪L2L。命題得證＃

(a).求證L1∪L2是右線性語(yǔ)言1212024/9/13

構(gòu)造G＝（N，T，P，S）其中N＝N1UN2，S＝S1，生成式P為:若A->αB∈P1，則它也屬于P 若A->α∈P1，則A->αS2∈P P2P先證L(G1).L(G2)L(G)

若有任意S1＝>*ω1

與S2＝>*ω2分別屬于G1和G2定義的語(yǔ)言中，那么有S1＝>α1A＝>α2B＝>α3C＝>…＝>ω1

和

S2＝>β1A1＝>β2B2＝>β3C3＝>…＝>ω2

，∴S＝>S1＝>α1A＝>α2B＝>α3C＝>…＝>ω1.S2＝>*ω1.ω2

∴L(G1).L(G2)L(G)(b).求證L1L2是右線性語(yǔ)言1222024/9/13

再證L(G)

L(G1).L(G2)若有S＝>S1＝>α1A＝>α2B＝>α3C＝>… ＝>ω1.S2＝>*ω1.ω2

那么則必然在G1和G2中同時(shí)有

S1＝>α1A＝>α2B＝>α3C＝>…＝>ω1

和

S2＝>β1A1＝>β2B2＝>β3C3＝>…＝>ω2∴L(G)L(G1).L(G2)命題得證＃

(b).求證L1.L2是右線性語(yǔ)言1232024/9/13

證明:構(gòu)造G＝（N，T，P，S）其中；N＝N1US，

SN1，S是一個(gè)新的非終結(jié)符，生成式P為: 如果A->

αB∈P1，則A->

αB∈P。 如果A->

α∈P1，則A->

αS∈P S->S1，S->ε∈P。先證L(G)

L(G1)*若有S＝>S1＝>ω1S＝>*ω1ω2S＝>… ＝>*ω1ω2…ωi.S＝>ω1ω2…ωi則在G1中必然有

S1＝>*ω1

；S1＝>*ω2；。。。；S1＝>*ωi∴L(G)L(G1)*(c).求證L1*是右線性語(yǔ)言1242024/9/13

再證L(G1)*

L(G)若G1中有

S1＝>*ω1

；S1＝>*ω2；。。。；S1＝>*ωi則在G中必然有S＝>S1＝>ω1S＝>*ω1ω2S＝>… ＝>*ω1ω2…ωi.S＝>ω1ω2…ωi∴L(G1)*L(G) 因此L*可以用右線性文法描述。證畢＃(c).求證L1*是右線性語(yǔ)言(續(xù))1252024/9/13

思路：

由給定的右線性文法可找出正則式，而正則式表示的語(yǔ)言即為正則集。方法：對(duì)右線性文法構(gòu)造標(biāo)準(zhǔn)形式的正規(guī)表達(dá)式方程組，應(yīng)用規(guī)則x＝αx+β＝>x＝α*β進(jìn)行消元，求解方程組，即可得出正規(guī)表達(dá)式。由(一)和(二)即可得出下定理:定理:

一個(gè)語(yǔ)言是正則集，當(dāng)且僅當(dāng)該語(yǔ)言為右線性語(yǔ)言。(二).證明由右線性文法產(chǎn)生的語(yǔ)言是正則集1262024/9/13

3.7正則表達(dá)式與有限自動(dòng)機(jī)的關(guān)系結(jié)論:有限自動(dòng)機(jī)、右（左）線性文法、正則表達(dá)式都定義