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

形式語(yǔ)言與自動(dòng)機(jī)第1頁(yè)，共38頁(yè)，2023年，2月20日，星期六22023/4/21CollegeofComputerScience&Technology,BUPT-NFA的形式定義一個(gè)-NFA

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

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

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

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

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

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

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

2Q第2頁(yè)，共38頁(yè)，2023年，2月20日，星期六32023/4/21CollegeofComputerScience&Technology,BUPT-NFA如何接受輸入符號(hào)串q1q0q2q3q5,+,–q4

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

3.14

+.314

–314.第3頁(yè)，共38頁(yè)，2023年，2月20日，星期六42023/4/21CollegeofComputerScience&Technology,BUPT二、-閉包（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}第4頁(yè)，共38頁(yè)，2023年，2月20日，星期六52023/4/21CollegeofComputerScience&Technology,BUPT狀態(tài)子集I的ε-閉包：

ε-CLOSURE(I)＝

∪

ε-CLOSURE(q)q∈I例：

ε-CLOSURE({q1，q2})＝ε-CLOSURE(q1)∪ε-CLOSURE(q2)＝{q1，q2}Ia概念：對(duì)于狀態(tài)子集IQ，任意a∈T，定義Ia如下：

Ia=ε-Closure(P)

其中P=δ（I，a）.即P是從I中的狀態(tài)經(jīng)過(guò)一條標(biāo)a的邊可以到達(dá)的狀態(tài)集合第5頁(yè)，共38頁(yè)，2023年，2月20日，星期六62023/4/21CollegeofComputerScience&Technology,BUPT例：I＝{q0，q1}，求I1I1

＝ε-CLOSURE（δ（I，1））＝ε-CLOSURE（δ（{q0，q1}，1））＝ε-CLOSURE（Φ∪{q1}）＝{q1，q2}q0q1q2012εε第6頁(yè)，共38頁(yè)，2023年，2月20日，星期六72023/4/21CollegeofComputerScience&Technology,BUPT擴(kuò)展轉(zhuǎn)移函數(shù)適合于輸入字符串設(shè)一個(gè)-NFA,

:QT

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).第7頁(yè)，共38頁(yè)，2023年，2月20日，星期六82023/4/21CollegeofComputerScience&Technology,BUPTε-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}第8頁(yè)，共38頁(yè)，2023年，2月20日，星期六92023/4/21CollegeofComputerScience&Technology,BUPT三、-NFA

的

語(yǔ)言

設(shè)一個(gè)-NFAM=(Q,

T,,q0,F)

定義M

的語(yǔ)言：

L(M)=ω|(q0

,ω)

F

即

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

第9頁(yè)，共38頁(yè)，2023年，2月20日，星期六102023/4/21CollegeofComputerScience&Technology,BUPT四、有轉(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ǔ)言.第10頁(yè)，共38頁(yè)，2023年，2月20日，星期六112023/4/21CollegeofComputerScience&Technology,BUPT從-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和δ1’是相等的。F1

＝F∪{q0}若ε-CLOSURE(q0)F F否則{第11頁(yè)，共38頁(yè)，2023年，2月20日，星期六122023/4/21CollegeofComputerScience&Technology,BUPT從-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）第12頁(yè)，共38頁(yè)，2023年，2月20日，星期六132023/4/21CollegeofComputerScience&Technology,BUPT設(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)（略）第13頁(yè)，共38頁(yè)，2023年，2月20日，星期六142023/4/21CollegeofComputerScience&Technology,BUPT證明同時(shí)展示了一種將-NFA轉(zhuǎn)化為NFA的方法.

-NFA

<==>

NFA

<==>

DFA例：將-NFA轉(zhuǎn)換為NFA.

（圖3.4.1，3.4.3）q0q1q2012εεq0q1q20120,11,20,1,2第14頁(yè)，共38頁(yè)，2023年，2月20日，星期六152023/4/21CollegeofComputerScience&Technology,BUPT舉例q1q0q2q3q5,+,–q4{q0}{q1}{q1q4}{q2}{q2q3q5}{q3q5}第15頁(yè)，共38頁(yè)，2023年，2月20日，星期六162023/4/21CollegeofComputerScience&Technology,BUPT第五節(jié)

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

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

聯(lián)合（union）

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

第16頁(yè)，共38頁(yè)，2023年，2月20日，星期六172023/4/21CollegeofComputerScience&Technology,BUPT正則表達(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上的正則集。

第17頁(yè)，共38頁(yè)，2023年，2月20日，星期六182023/4/21CollegeofComputerScience&Technology,BUPT正則表達(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è)正則式）第18頁(yè)，共38頁(yè)，2023年，2月20日，星期六192023/4/21CollegeofComputerScience&Technology,BUPT正則表達(dá)式舉例書(shū)p76例1表示如下語(yǔ)言的正則表達(dá)式：語(yǔ)言中的每個(gè)字符串由交替的0s和1s

構(gòu)成

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

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

(+0)(10)*(+1)第19頁(yè)，共38頁(yè)，2023年，2月20日，星期六202023/4/21CollegeofComputerScience&Technology,BUPT語(yǔ)言的聯(lián)合（union）運(yùn)算兩個(gè)語(yǔ)言L和M的聯(lián)合

L

M=wwLwM

舉例設(shè)L=001,10,111

,

M=,001,則

L

M=,10,001,111

第20頁(yè)，共38頁(yè)，2023年，2月20日，星期六212023/4/21CollegeofComputerScience&Technology,BUPT語(yǔ)言的連接（concatenation）運(yùn)算

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

L·

M=w1w2

w1

Lw2

M

有時(shí)記L·

M為L(zhǎng)M

舉例設(shè)L=001,10,111

,

M=,001,則

LM=001,10,111,001001,10001,111001第21頁(yè)，共38頁(yè)，2023年，2月20日，星期六222023/4/21CollegeofComputerScience&Technology,BUPT語(yǔ)言的閉包（closure）運(yùn)算語(yǔ)言L的閉包

L*=wn

wLn0

,其中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,…第22頁(yè)，共38頁(yè)，2023年，2月20日，星期六232023/4/21CollegeofComputerScience&Technology,BUPT正則式的性質(zhì)交換律（commutativity）和結(jié)合律（associativeity）(1)(α+β)+γ＝α+(β+γ)(2)(αβ)γ＝α(βγ)(3)α+β＝β+α等冪律（idempotentlaw）(4)α+α＝α分配律（distributivelaw）(5)α(β+γ)＝αβ+αγ(6)(β+γ)α＝βα+γα第23頁(yè)，共38頁(yè)，2023年，2月20日，星期六242023/4/21CollegeofComputerScience&Technology,BUPT正則式的性質(zhì)幺元（identities）和零元（annihilators）(7)α+φ＝φ+α＝α(8)αφ＝φα＝φ(9)αε＝εα＝α

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

*=*=L+=LL*=L*L（L+的定義）L*=L++第24頁(yè)，共38頁(yè)，2023年，2月20日，星期六252023/4/21CollegeofComputerScience&Technology,BUPT正則式的性質(zhì)(11)α*＝α+α*

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

L(α*)＝{ε}∪L(α)∪L(α2)∪…∪L(αn)L(α+α*)＝L(α)∪({ε}∪L(α)∪L(α2) ∪…∪L(αn))

＝L(α)∪L(α*)而L(α)L(α*)∴α+α*＝α*第25頁(yè)，共38頁(yè)，2023年，2月20日，星期六262023/4/21CollegeofComputerScience&Technology,BUPT右線性文法與正則式

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

例：文法SaS，Sa 對(duì)應(yīng)正則式：a+，或者a*a第26頁(yè)，共38頁(yè)，2023年，2月20日，星期六272023/4/21CollegeofComputerScience&Technology,BUPT從右線性文法導(dǎo)出正則式求解規(guī)則:設(shè)x

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

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

αx

和x

β，生成的語(yǔ)言為（β，αβ，ααβ，αααβ,…）,顯然該語(yǔ)言可用正則式α*β表示。 書(shū)p78，例2 書(shū)p79，例3第27頁(yè)，共38頁(yè)，2023年，2月20日，星期六282023/4/21CollegeofComputerScience&Technology,BUPT第六節(jié)正則集和右線性文法正則集是由右線性文法產(chǎn)生的語(yǔ)言由右線性文法產(chǎn)生的語(yǔ)言都是正則集(一).求證正則集是由右線性文法產(chǎn)生的語(yǔ)言證明方法：

找出相應(yīng)的右線性文法，使之產(chǎn)生的語(yǔ)言是這些正則集。第28頁(yè)，共38頁(yè)，2023年，2月20日，星期六292023/4/21CollegeofComputerScience&Technology,BUPT首先從最簡(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}

第29頁(yè)，共38頁(yè)，2023年，2月20日，星期六302023/4/21CollegeofComputerScience&Technology,BUPT將對(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)換名)第30頁(yè)，共38頁(yè)，2023年，2月20日，星期六312023/4/21CollegeofComputerScience&Technology,BUPT構(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ǔ)言第31頁(yè)，共38頁(yè)，2023年，2月20日，星期六322023/4/21CollegeofComputerScience&Technology,BUPT

構(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ǔ)言第32頁(yè)，共38頁(yè)，2023年，2月20日，星期六332023/4/21CollegeofComputerScience&Technology,BUPT

再證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ǔ)言第33頁(yè)，共38頁(yè)，2023年，2月20日，星期六342023/4/21CollegeofComputerScience&Technology,BUPT證明:構(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＝>…