版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認領(lǐng)
文檔簡介
形式語言與自動機第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=>
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 電動包餃子機相關(guān)項目實施方案
- 游泳池娛樂用品相關(guān)項目實施方案
- 潤唇膏項目可行性實施報告
- 電動高爾夫球車市場環(huán)境與對策分析
- 燈芯剪剪刀項目評價分析報告
- 浴衣市場環(huán)境與對策分析
- 成都師范學(xué)院《舞臺藝術(shù)實踐》2022-2023學(xué)年第一學(xué)期期末試卷
- 球拍用吸汗帶項目評價分析報告
- 成都師范學(xué)院《水文學(xué)與水資源》2022-2023學(xué)年第一學(xué)期期末試卷
- 成都師范學(xué)院《三維建模技術(shù)》2021-2022學(xué)年第一學(xué)期期末試卷
- 康復(fù)輔助器具的使用與指導(dǎo)
- 初中體育運動損傷的預(yù)防與處理
- 曼浦漢克化工(上虞)有限公司年產(chǎn)1500噸氧化鉍(利用新工藝)項目環(huán)境影響報告書
- 《渠道管理與拓展》課件
- 智能家居的產(chǎn)品設(shè)計
- 胸中天地寬 常有渡人船 -主題班會課件
- Unit6Craftsmanship+Listening+an課件-中職高教版(2021)基礎(chǔ)模塊2
- 港口碼頭租賃協(xié)議書
- 壓力容器周檢查表
- 班委會議記錄表
- 數(shù)字孿生故障診斷與預(yù)測
評論
0/150
提交評論