形式語言自動機(jī)有限自動機(jī)

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

一個人帶著一頭狼，一頭羊，以及一棵青菜，處于河的左岸。有一條小船,每次只能攜帶人和其余的三者之一。人和他的伴隨品都希望渡到河的右岸，而每擺渡一次，人僅能帶其中之一。然而如果人留下狼和羊不論在左岸還是在右岸，狼肯定會吃掉羊。類似地，如果單獨(dú)留下羊和菜，羊也肯定會吃掉菜。如何才能既渡過河而羊和菜又不被吃掉呢?2CollegeofComputerScience&Technology,BUPTMG－WC（處于左岸的子集－處于右岸的子集）將過河問題模型化：人(M)狼(W)羊(G)菜(C)3CollegeofComputerScience&Technology,BUPT二、有限自動機(jī)的概念有限自動機(jī)的概念具有離散輸入輸出系統(tǒng)的一種數(shù)學(xué)模型

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

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

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

NFA4CollegeofComputerScience&Technology,BUPTFA的模型FA可以理解成一個控制器,它讀一條輸入帶上的字符。101101有限控制器(1)

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

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

狀態(tài)+激勵

狀態(tài)遷移

(根據(jù)當(dāng)前所處狀態(tài)和輸入字符進(jìn)行狀態(tài)轉(zhuǎn)移)5CollegeofComputerScience&Technology,BUPT有限狀態(tài)集

有限輸入符號集

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

一個開始狀態(tài)

一個終態(tài)集合有限自動機(jī)的五要素q0q1q2q36CollegeofComputerScience&Technology,BUPT三、DFA的形式定義定義:

DFA是一個五元組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表示方法：

7CollegeofComputerScience&Technology,BUPT轉(zhuǎn)移圖表示的DFA

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}q0q1q2q38CollegeofComputerScience&Technology,BUPT轉(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}9CollegeofComputerScience&Technology,BUPT四、擴(kuò)展轉(zhuǎn)移函數(shù)適合于輸入字符串δ’函數(shù)：接收一個字符串的狀態(tài)轉(zhuǎn)移函數(shù)。

:QT*Q

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

對于DFA:δ’(q,a)=δ(δ‘(q,

),a)=δ(q,a)，即對于單個字符時δ和δ'是相等的。為了方便，以后在不引起混淆時用δ代替δ'10CollegeofComputerScience&Technology,BUPT擴(kuò)展轉(zhuǎn)移函數(shù)適合于輸入字符串

q0q1q2

q301q2q1q3q0q0q3q1q2舉例

(q0,

)

=q0(q0,0)

=(q0,0)

=q2(q0,00)

=(q2,0)

=q0(q0,001)

=(q0,1)

=q1(q0,0010)

=(q1,0)

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

ω

(q0,ω)F

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

F13CollegeofComputerScience&Technology,BUPT如圖，接受001010的格局（q0,001010）┝(q2,01010)┝(q0,1010)┝(q1,010)┝(q3,10)┝(q2,0)┝(q0,ε)格局?jǐn)?shù)量是無限的。有限狀態(tài)自動機(jī)是無記憶的。例如接受0010101111和接受01011111時，都可以進(jìn)入格局(q0,1111)。格局示例q0q1q2q314CollegeofComputerScience&Technology,BUPT設(shè)計(jì)有限自動機(jī)自動機(jī)的設(shè)計(jì)是一個創(chuàng)造過程，沒有簡單的算法或過程。技巧：假設(shè)自己是機(jī)器，思考如何去實(shí)現(xiàn)機(jī)器的任務(wù)。為判斷到目前為止所看到的字符串是否滿足某個語言，須估算出讀一個字符串時需要記住哪些關(guān)鍵的東西。（找出狀態(tài)）

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

q偶a偶bq奇a偶bq偶a奇bq奇a奇bStartbaabaabb15CollegeofComputerScience&Technology,BUPT設(shè)計(jì)有限自動機(jī)例2：構(gòu)造有限自動機(jī)M，識別{0,1}上的語言L={x000y|x,y∈{0.1}*}分析：該語言特點(diǎn)是每個串都包含連續(xù)3個0的子串，自動機(jī)的任務(wù)是識別/檢查是否存在子串000。 由于字符是逐一讀入，當(dāng)讀入一個0時，就需記住（狀態(tài)q1), 若接著讀入的還是0，則需記住已讀入連續(xù)的2個0了（狀態(tài)q2),若接著讀入的還是0，則需記住已讀入連續(xù)的2個0了（狀態(tài)q3),16CollegeofComputerScience&Technology,BUPT設(shè)計(jì)有限自動機(jī)例3：構(gòu)造有限自動機(jī)M，識別{0,1,2}上的語言,每個字符串代表的數(shù)字能整除3。分析：如果一個十進(jìn)制數(shù)的所有位的數(shù)字之和能整除3，則該十進(jìn)制數(shù)就能整除3。 一個十進(jìn)制數(shù)除以3，余數(shù)只能為0、1、2。---設(shè)計(jì)為狀態(tài)。狀態(tài)q0表示已讀入的數(shù)字和除3余0,狀態(tài)q1表示已讀入的數(shù)字和除3余1,狀態(tài)q2表示已讀入的數(shù)字和除3余2,17CollegeofComputerScience&Technology,BUPT第二節(jié) 不確定的有限自動機(jī)(NFA) 修改DFA的模型,使之在某個狀態(tài),對應(yīng)一個輸入,可以有多個轉(zhuǎn)移,到達(dá)不同的狀態(tài),則稱為不確定的有限自動機(jī)。

例：(1)(2)18CollegeofComputerScience&Technology,BUPT一、不確定有限自動機(jī)的形式定義NFA是一個五元組,M=(Q,T,δ,q0,F).

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

則稱NFA接收該字符串.19CollegeofComputerScience&Technology,BUPT(1)(2)pq

r0{q}

{q}

{q,r}

1pq

r0{p}{r}

{r}

1{p,q}轉(zhuǎn)移圖和轉(zhuǎn)移表表示的NFA注意：轉(zhuǎn)移表中的每一項(xiàng)都是一個集合。含空集Φ20CollegeofComputerScience&Technology,BUPT二、NFA的狀態(tài)轉(zhuǎn)移函數(shù)與DFA唯一不同之處:Q

T

2Q同樣,δ可擴(kuò)展為δ’

(

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

=

{q}

含義:

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

即若(q,ω)={r

1,r

2,,r

k},則

(q,ωa)=(r

i,a)其中ω

T*,a

T，r

i

Q21CollegeofComputerScience&Technology,BUPT舉例

(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ù)適合于輸入字符串22CollegeofComputerScience&Technology,BUPTNFA

接受的語言

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

T,

,q0,F)

定義A的語言：

L(A)=

ω

(q0,ω)

F

23CollegeofComputerScience&Technology,BUPT第三節(jié)

NFA與DFA的等價性為什么要討論等價性？問題的提出NFA識別語言的復(fù)雜性，參見教材P59的例子。需回溯和智能才能識別句子。DFA具有結(jié)構(gòu)簡單清晰的特點(diǎn)。是否存在NFA--〉DFA的轉(zhuǎn)換方法？如果找到這樣的轉(zhuǎn)換方法，是否正確和普適？一般研究方法：找到一種方法（構(gòu)造方法）或性質(zhì)，然后證明該方法/性質(zhì)的正確性。所謂定理就是被證明是正確的性質(zhì)。24CollegeofComputerScience&Technology,BUPT第三節(jié)

NFA與DFA的等價性DFA是NFA的特例,

所以NFA必然能接收DFA能接收的語言.

因此證明等價性只要能夠證明一個NFA所能接收的語言必能被另一個DFA所接收。關(guān)鍵問題：是否能構(gòu)造出這樣的DFA？分析思路：基于

:Q

T

2Q

，將轉(zhuǎn)移后的“集合”作為新的狀態(tài)，表示為{q1,q2,…qm},注意：集合-狀態(tài)。新的轉(zhuǎn)移函數(shù)的構(gòu)造。新的終止?fàn)顟B(tài)集合的確定25CollegeofComputerScience&Technology,BUPT第三節(jié)

NFA與DFA的等價性1.定理:

設(shè)一個NFA接受語言L,

那么必然存在一個DFA接受L。2.

證明:策略:對于任意一個NFA,構(gòu)造一個接收它所能接收語言的DFA，這個DFA的狀態(tài)對應(yīng)了NFA的狀態(tài)集合。即NFA冪集的元素。26CollegeofComputerScience&Technology,BUPT從NFA構(gòu)造等價的

DFA(子集構(gòu)造法)設(shè)L是某個NFAN=(QN,

T,

N,q0,FN)的語言,則存在一個DFAM,滿足L(M)=L(N)=L.

證明:定義

M=(QD,

T,

D,{q0},FD

),

其中

QD

=

S

S

QN

=2Q注意：S是集合

對S

QD

和aT

,

D(S,a)=

N(q,a).

FD=

S

S

QN

S

FN

需要證明:對任何ω

T*

,

D({q0}

,ω)=

N(q0,ω).

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

S27CollegeofComputerScience&Technology,BUPTpq

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)造法舉例1、初始的NFA2、子集構(gòu)造，計(jì)算狀態(tài)可達(dá)3、經(jīng)篩選后的DFA28CollegeofComputerScience&Technology,BUPTpq

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)造法舉例29CollegeofComputerScience&Technology,BUPT證明:從

NFA構(gòu)造等價的

DFA設(shè)N=(QN,

T,

N,q0,FN)是一個NFA

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

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

T,

D,[q0],FD

),則對任何ω

T*

,

D({q0}

,ω)=

N(q0,ω).

證明:歸納于|ω|1設(shè)|ω

|=0,即

ω=

.由定義知

D({q0},

)=

N(q0,

)={q0}.2

設(shè)|ω

|=n+1,并

ω

=xa,a

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

D({q0}

,x)=

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

,pk

}.則

D({q0}

,ω)=

D(

D({q0}

,x),a)=

D({p1,p2,

,pk

},a)=

N(pi,a).=

N(q0,ω)i=1k30CollegeofComputerScience&Technology,BUPT

實(shí)踐中,通過子集構(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ù)q0q1q2qn31CollegeofComputerScience&Technology,BUPT第四節(jié) 有

轉(zhuǎn)換的NFA為什么會引出帶ε轉(zhuǎn)換的NFA？與NFA的目的一樣，也是為了表達(dá)簡單直觀。例１：表示接受字符串或由若干個0,或接若干個1,或再接若干個2的自動機(jī)？問題：如何構(gòu)造／設(shè)計(jì)這個自動機(jī)呢？q0q1q2012εε32CollegeofComputerScience&Technology,BUPT第四節(jié) 有

轉(zhuǎn)換的NFA為什么會引出帶ε轉(zhuǎn)換的NFA？（續(xù)）可以用來識別關(guān)鍵字集合，程序語言中的應(yīng)用例２：設(shè)計(jì)識別關(guān)鍵字web,ebay.問題：如何構(gòu)造／設(shè)計(jì)這個自動機(jī)呢？33CollegeofComputerScience&Technology,BUPT第四節(jié) 有

轉(zhuǎn)換的NFA一、定義 概念:當(dāng)輸入空串ε(無輸入)時，也能引起狀態(tài)的轉(zhuǎn)移.例：輸入“002”時的轉(zhuǎn)移格局：

q0q1q2012εε34CollegeofComputerScience&Technology,BUPT

-NFA的形式定義一個

-NFA

是一個五元組A=(Q,

T,

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

有限輸入符號集

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

一個開始狀態(tài)

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

Q

F

Q與NFA的不同之處

:Q(T

)

2Q35CollegeofComputerScience&Technology,BUPT

-NFA的形式定義δ(q0，0)={q0}, δ(q0，1)=Φ,δ(q0，2)=Φ, δ(q0，ε)={q1},δ(q1，0)=Φ, δ(q1，1)={q1},δ(q1，2)=Φ, δ(q1，ε)={q2},δ(q2，0)=Φ, δ(q2，1)=Φ,δ(q2，2)={q2}, δ(q2，ε)=Φ,q0q1q2012εε36CollegeofComputerScience&Technology,BUPT

-NFA如何接受輸入符號串q1q0q2q3q5

,+,–q4

該

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

3.14

+.314

–314.37CollegeofComputerScience&Technology,BUPT二、

-閉包（closure）概念定義1：狀態(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}38CollegeofComputerScience&Technology,BUPT定義2：狀態(tài)子集I的ε-閉包： ε-CLOSURE(I)＝

∪

ε-CLOSURE(q)或

q∈I

={ε-CLOSURE(q)|q∈I

}

例：ε-CLOSURE({q1，q2})＝ε-CLOSURE(q1)∪ε-CLOSURE(q2)＝{q1，q2}39CollegeofComputerScience&Technology,BUPT

Ia

概念：對于狀態(tài)子集I

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

Ia=ε-Closure(P)

其中P=δ（I，a）.即P是從I中的狀態(tài)經(jīng)過一條標(biāo)a的邊可以到達(dá)的狀態(tài)集合40CollegeofComputerScience&Technology,BUPT例：I＝{q0，q1}，求I1I1＝ε-CLOSURE（δ（I，1））＝ε-CLOSURE（δ（{q0，q1}，1））＝ε-CLOSURE（Φ∪{q1}）＝{q1，q2}q0q1q2012εε41CollegeofComputerScience&Technology,BUPT擴(kuò)展轉(zhuǎn)移函數(shù)適合于輸入字符串設(shè)一個

-NFA,

:Q

T

2Q

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

對任何qQ，定義：1(q,)=ε-CLOSURE(q)2δ'(q,a)＝ε-CLOSURE(P)=ε-CLOSURE(δ(δ’(q,ε),a))3δ'(q，ωa)＝ε-CLOSURE(P)其中：P＝{p|存在r∈δ'(q，ω)∧p∈δ(r，a)}注意：此時δ(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).42CollegeofComputerScience&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}43CollegeofComputerScience&Technology,BUPT三、-NFA

的

語言

設(shè)一個

-NFAM=(Q,

T,

,q0,F)

定義M

的語言：

L(M)=

ω|(q0

,ω)

F

即

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

44CollegeofComputerScience&Technology,BUPT四、

-NFA與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所接受的語言.45CollegeofComputerScience&Technology,BUPT從

-NFA構(gòu)造等價的無

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

,q0,F)是一個

-NFA,可構(gòu)造一個無

的NFAM1=(Q,T,

1

,q0,F1),構(gòu)造思路：狀態(tài)集合不變；轉(zhuǎn)移函數(shù)的構(gòu)造；對任何aT,

1(q,a)=

(q

,a)---構(gòu)造方法

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

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

F

F否則{46CollegeofComputerScience&Technology,BUPT從

-NFA構(gòu)造等價的無

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

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

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

而δ’(q0，ε)＝ε-CLOSURE(q0)

因此，從|ω|＝1開始證明當(dāng)|ω|=1時，定義相等。 由δ