形式語言與自動機

形式語言與自動機第1頁，課件共38頁，創(chuàng)作于2023年2月22023/7/23CollegeofComputerScience&Technology,BUPT-NFA的形式定義一個-NFA

是一個五元組A=(Q,

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

有限輸入符號集

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

一個開始狀態(tài)

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

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

2Q第2頁，課件共38頁，創(chuàng)作于2023年2月32023/7/23CollegeofComputerScience&Technology,BUPT-NFA如何接受輸入符號串q1q0q2q3q5,+,–q4

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

3.14

+.314

–314.第3頁，課件共38頁，創(chuàng)作于2023年2月42023/7/23CollegeofComputerScience&Technology,BUPT二、-閉包（closure）概念

狀態(tài)q的-閉包，記為

-

CLOSURE或ECLOSE

，定義為從q經(jīng)所有的路徑可以到達的狀態(tài)（包括q自身），如：

q0q1q2012εε

-CLOSURE

(q0)={q0,q1,q2}

-CLOSURE

(q1)={q1,q2}

-CLOSURE

(q2)=

{q2}第4頁，課件共38頁，創(chuàng)作于2023年2月52023/7/23CollegeofComputerScience&Technology,BUPT狀態(tài)子集I的ε-閉包：

ε-CLOSURE(I)＝

∪

ε-CLOSURE(q)q∈I例：

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

Ia=ε-Closure(P)

其中P=δ（I，a）.即P是從I中的狀態(tài)經(jīng)過一條標a的邊可以到達的狀態(tài)集合第5頁，課件共38頁，創(chuàng)作于2023年2月62023/7/23CollegeofComputerScience&Technology,BUPT例：I＝{q0，q1}，求I1I1

＝ε-CLOSURE（δ（I，1））＝ε-CLOSURE（δ（{q0，q1}，1））＝ε-CLOSURE（Φ∪{q1}）＝{q1，q2}q0q1q2012εε第6頁，課件共38頁，創(chuàng)作于2023年2月72023/7/23CollegeofComputerScience&Technology,BUPT擴展轉(zhuǎn)移函數(shù)適合于輸入字符串設(shè)一個-NFA,

:QT

2Q

擴充定義:QT*2Q

對任何qQ，定義：1(q,)=ECLOSE(q)2δ'(q，ωa)＝ε-CLOSURE(P)其中P＝{p|存在r∈δ'(q，ω)∧p∈δ(r，a)}注意：此時δ(q，a)δ'(q，a)，因為δ(q，a)表示由q出發(fā)，只沿著標a的路徑所能到達的狀態(tài)，而δ'(q，a)表示由q出發(fā)，沿著標a(包括ε轉(zhuǎn)換在內(nèi))的路徑所能到達的狀態(tài).第7頁，課件共38頁，創(chuàng)作于2023年2月82023/7/23CollegeofComputerScience&Technology,BUPTε-NFA中，δ與δ’函數(shù)的不同

舉例計算(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頁，課件共38頁，創(chuàng)作于2023年2月92023/7/23CollegeofComputerScience&Technology,BUPT三、-NFA

的

語言

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

T,,q0,F)

定義M

的語言：

L(M)=ω|(q0

,ω)

F

即

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

第9頁，課件共38頁，創(chuàng)作于2023年2月102023/7/23CollegeofComputerScience&Technology,BUPT四、有轉(zhuǎn)換的NFA與無轉(zhuǎn)換的NFA的等價1.

-NFA<==>NFA

具有轉(zhuǎn)移的NFA是不具轉(zhuǎn)移的NFA的一般情況,

所以只要證明下面的定理即可:定理:

如果L被一個具有轉(zhuǎn)移的NFA接收,

那么L可被一個不具轉(zhuǎn)移的NFA接收.證明思路:構(gòu)造一個不具轉(zhuǎn)移的NFA,證明其接收具有轉(zhuǎn)移的NFA所接受的語言.第10頁，課件共38頁，創(chuàng)作于2023年2月112023/7/23CollegeofComputerScience&Technology,BUPT從-NFA構(gòu)造等價的無NFA設(shè)M=(Q,T,

,q0,F)是一個-NFA,可構(gòu)造一個無的NFAM1=(Q,T,1

,q0,F1),對任何aT,1(q,a)=

(q

,a).

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

＝F∪{q0}若ε-CLOSURE(q0)F F否則{第11頁，課件共38頁，創(chuàng)作于2023年2月122023/7/23CollegeofComputerScience&Technology,BUPT從-NFA構(gòu)造等價的無NFA證明:采用歸納法證明δ1（q0，ω）＝δ’（q0，

ω），|ω|>=1。當|w|=0,即w=時，不一定相等.∵δ1(q0，ε)＝{q0}， 而δ’(q0，ε)＝ε-CLOSURE(q0) 因此，從|ω|＝1開始證明當|ω|=1時，定義相等。 由δ1定義

δ1（q0，a）＝δ’（q0，a）第12頁，課件共38頁，創(chuàng)作于2023年2月132023/7/23CollegeofComputerScience&Technology,BUPT設(shè)當|ω|<=n時，δ1（q0,ω）=δ’（q0,ω），則當|ωa|=n+1時，左側(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的一個狀態(tài)當且僅當δ’（q0，ω）含F(xiàn)的一個狀態(tài)（略）第13頁，課件共38頁，創(chuàng)作于2023年2月142023/7/23CollegeofComputerScience&Technology,BUPT證明同時展示了一種將-NFA轉(zhuǎn)化為NFA的方法.

-NFA

<==>

NFA

<==>

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

（圖3.4.1，3.4.3）q0q1q2012εεq0q1q20120,11,20,1,2第14頁，課件共38頁，創(chuàng)作于2023年2月152023/7/23CollegeofComputerScience&Technology,BUPT舉例q1q0q2q3q5,+,–q4{q0}{q1}{q1q4}{q2}{q2q3q5}{q3q5}第15頁，課件共38頁，創(chuàng)作于2023年2月162023/7/23CollegeofComputerScience&Technology,BUPT第五節(jié)

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

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

聯(lián)合（union）

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

第16頁，課件共38頁，創(chuàng)作于2023年2月172023/7/23CollegeofComputerScience&Technology,BUPT正則表達式（regularexpression）歸納定義正則表達式如下：基礎(chǔ)：ε，φ，a

（a∈T）都是正則式(原子正則式)， 相應(yīng)的正則集為{ε}，φ，{a}歸納：如果A和B是正則式，且分別代表集合L(A)和L(B)，則(A+B)，(A.B),A*也是正則式，分別表示以下正則集.L(A)∪L(B)(語言A/語言B的串)L(A).L(B) (兩個語言中的串的連接)L(A)* (語言A中的串的多次連接)僅通過有限次使用以上兩步定義的表達式，才是字母表T上的正則式。這些正則式所表示的字符串集合是T上的正則集。

第17頁，課件共38頁，創(chuàng)作于2023年2月182023/7/23CollegeofComputerScience&Technology,BUPT正則表達式算符優(yōu)先級算符優(yōu)先級（precedence）依次為

（closure

）

?連接（concatenation）

（union）定義：若兩個正則式表示相同的正則集，則稱這兩個正則式相等。即R1＝R2<==>L(R1)=L(R2)注1：正則集是T*的子集。注2：L+包含ε當且僅當L包含ε。注3：每個正則集至少對應(yīng)一個正則式（可有無窮多個正則式）第18頁，課件共38頁，創(chuàng)作于2023年2月192023/7/23CollegeofComputerScience&Technology,BUPT正則表達式舉例書p76例1表示如下語言的正則表達式：語言中的每個字符串由交替的0s和1s

構(gòu)成

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

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

(+0)(10)*(+1)第19頁，課件共38頁，創(chuàng)作于2023年2月202023/7/23CollegeofComputerScience&Technology,BUPT語言的聯(lián)合（union）運算兩個語言L和M的聯(lián)合

L

M=wwLwM

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

,

M=,001,則

L

M=,10,001,111

第20頁，課件共38頁，創(chuàng)作于2023年2月212023/7/23CollegeofComputerScience&Technology,BUPT語言的連接（concatenation）運算

兩個語言L和M的連接

L·

M=w1w2

w1

Lw2

M

有時記L·

M為LM

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

,

M=,001,則

LM=001,10,111,001001,10001,111001第21頁，課件共38頁，創(chuàng)作于2023年2月222023/7/23CollegeofComputerScience&Technology,BUPT語言的閉包（closure）運算語言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頁，課件共38頁，創(chuàng)作于2023年2月232023/7/23CollegeofComputerScience&Technology,BUPT正則式的性質(zhì)交換律（commutativity）和結(jié)合律（associativeity）(1)(α+β)+γ＝α+(β+γ)(2)(αβ)γ＝α(βγ)(3)α+β＝β+α等冪律（idempotentlaw）(4)α+α＝α分配律（distributivelaw）(5)α(β+γ)＝αβ+αγ(6)(β+γ)α＝βα+γα第23頁，課件共38頁，創(chuàng)作于2023年2月242023/7/23CollegeofComputerScience&Technology,BUPT正則式的性質(zhì)幺元（identities）和零元（annihilators）(7)α+φ＝φ+α＝α(8)αφ＝φα＝φ(9)αε＝εα＝α

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

*=*=L+=LL*=L*L（L+的定義）L*=L++第24頁，課件共38頁，創(chuàng)作于2023年2月252023/7/23CollegeofComputerScience&Technology,BUPT正則式的性質(zhì)(11)α*＝α+α*

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

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

＝L(α)∪L(α*)而L(α)L(α*)∴α+α*＝α*第25頁，課件共38頁，創(chuàng)作于2023年2月262023/7/23CollegeofComputerScience&Technology,BUPT右線性文法與正則式

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

例：文法SaS，Sa 對應(yīng)正則式：a+，或者a*a第26頁，課件共38頁，創(chuàng)作于2023年2月272023/7/23CollegeofComputerScience&Technology,BUPT從右線性文法導(dǎo)出正則式求解規(guī)則:設(shè)x

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

=αx+β表示x有兩個生成式:x

αx

和x

β，生成的語言為（β，αβ，ααβ，αααβ,…）,顯然該語言可用正則式α*β表示。 書p78，例2 書p79，例3第27頁，課件共38頁，創(chuàng)作于2023年2月282023/7/23CollegeofComputerScience&Technology,BUPT第六節(jié)正則集和右線性文法正則集是由右線性文法產(chǎn)生的語言由右線性文法產(chǎn)生的語言都是正則集(一).求證正則集是由右線性文法產(chǎn)生的語言證明方法：

找出相應(yīng)的右線性文法，使之產(chǎn)生的語言是這些正則集。第28頁，課件共38頁，創(chuàng)作于2023年2月292023/7/23CollegeofComputerScience&Technology,BUPT首先從最簡單的正則式出發(fā)，求證其正則集Φ，{ε}，{a}是右線性語言。證明:對正則集Φ，有右線性文法G＝{{S}，T，Φ，S}，使L(G)=Φ對正則集{ε},有右線性文法G＝{{S}，T，{S->ε}，S}，使L(G)={ε}對正則集{a}，有右線性文法G＝{{S}，T，{S->a}，S}，使L(G)={a}

第29頁，課件共38頁，創(chuàng)作于2023年2月302023/7/23CollegeofComputerScience&Technology,BUPT將對由并，積，閉包形成的正則集的證明，改為對右線性語言的證明。 設(shè)在字母表T上，有語言L1和L2，則L1∪L2，L1.L2，L1*都是右線性語言。證明方法：分別找出相應(yīng)的右線性文法。設(shè)G1＝（N1，T，P1，S1）產(chǎn)生L1G2＝（N2，T，P2，S2）產(chǎn)生L2N1N2＝Φ(若不為空,則可對N中符號換名)第30頁，課件共38頁，創(chuàng)作于2023年2月312023/7/23CollegeofComputerScience&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的定義，對于任意ω，意味著或者（按G1的產(chǎn)生式），或者（按G2的產(chǎn)生式）即文法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是右線性語言第31頁，課件共38頁，創(chuàng)作于2023年2月322023/7/23CollegeofComputerScience&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定義的語言中，那么有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是右線性語言第32頁，課件共38頁，創(chuàng)作于2023年2月332023/7/23CollegeofComputerScience&Technology,BUPT

再證L(G)

L(G1).L(G2)若有S＝>S1

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

＝>ω1.S2

＝>*ω1.ω2

那么則必然在G1和G2中同時有

S1

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

和

S2

＝>β1A1＝>β2B2

＝>β3C3

＝>…＝>ω2∴L(G)L(G1).L(G2)命題得證＃

(b).求證L1.L2是右線性語言第33頁，課件共38頁，創(chuàng)作于2023年2月342023/7/23CollegeofComputerScience&Technology,BUPT證明:構(gòu)造G＝（N，T，P，S）其中；N＝N1US，SN1，S是一個新的非終結(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＝>