(15)第二章-第八講-雙向和有輸出的有限自動(dòng)機(jī)

第二章

有限自動(dòng)機(jī)和右線性文法

第八講

雙向和有輸出的有限自動(dòng)機(jī)一、雙向有限自動(dòng)機(jī)

本章第一講中介紹的有限自動(dòng)機(jī)的輸入帶上的讀頭只能從左向右移動(dòng)，每輸入一個(gè)字符讀頭就向右移動(dòng)一格。

所謂雙向有限自動(dòng)機(jī)是指每輸入一個(gè)字符時(shí)輸入帶上的讀頭既可以往左移動(dòng)，也可以往右移動(dòng)，甚至于不移動(dòng)。本講不討論不移動(dòng)的情況。一、雙向有限自動(dòng)機(jī)

M=(Q,T,δ,q0,F),其中：

例如：

δ(q1,a)={q2,L}表明當(dāng)讀入字符a時(shí)2DFA的狀態(tài)從q1轉(zhuǎn)換到q2，且讀頭往左移動(dòng)一格；1.

確定的雙向有限自動(dòng)機(jī)

(2DFA)M的形式定義

與DFA相比，只有轉(zhuǎn)換函數(shù)δ不同：δ：是從Q×T到Q×{L,R}的映射。

δ(q1,a)={q2,R}則表明當(dāng)讀入字符a時(shí)2DFA的狀態(tài)從q1轉(zhuǎn)換到q2，且讀頭往右移動(dòng)一格；一、雙向有限自動(dòng)機(jī)2.

用“格局”描述2DFA的瞬時(shí)變化重要回顧：原始的有限自動(dòng)機(jī)中格局的定義：定義2

設(shè)有限自動(dòng)機(jī)M=(Q,T,δ,q0,F),

對(duì)偶(q,w)∈Q×T*稱為M的格局，并稱(q0,w)為初始格局；對(duì)于q∈F,稱(q,ε)為終止格局或接受格局。

若當(dāng)前狀態(tài)為q，當(dāng)前讀入字符為a，若有狀態(tài)轉(zhuǎn)換函數(shù)δ(q,a)=q1,則狀態(tài)變換后的后繼狀態(tài)為q1，此時(shí)可用格局變化形式描述這一變換過程：(q,aw)├─(q1,w)。一、雙向有限自動(dòng)機(jī)

格局形式：w1qw2w1w2

∈T*,q∈Q其中：w1w2

是輸入字符串w,w1

是當(dāng)前讀頭左邊的字符串部分,w2是當(dāng)前讀頭右邊的字符串部分,q是當(dāng)前狀態(tài),在格局中的位置亦表示輸入帶上讀頭的位置。2.

用“格局”描述2DFA的瞬時(shí)變化

當(dāng)w2=ε時(shí)，則表示讀頭已達(dá)到輸入字符串w的最右邊。

格局變化：當(dāng)格局為b1b2...bmq1bm+1...bn時(shí)，若有：

δ(q1,bm+1)=(q2,R),則有：b1b2...bmq1bm+1...bnb1b2...bmbm+1q2bm+2...bn

,一、雙向有限自動(dòng)機(jī)

對(duì)于一個(gè)確定的雙向自動(dòng)機(jī)M而言，它所接受的字符串w是在初始狀態(tài)q0時(shí)，從輸入字符串w的最左字符開始逐個(gè)讀入字符(中間可能經(jīng)過讀頭的左右移動(dòng)而使某些字符被多次讀取)，直至最后讀頭移動(dòng)到w的右邊且恰好進(jìn)入終止?fàn)顟B(tài)，則稱w被2DFAM所接受。3.2DFA所接受的句子及其所定義的語言

2DFAM所接受的句子的集合稱為2DFAM所定義的語言。記為：L(M)={w|q0w

wq,q∈F}一、雙向有限自動(dòng)機(jī)實(shí)例：設(shè)2DFAM=（{q0,q1,q2},{a,b},δ,q0,{q1})其中轉(zhuǎn)換函數(shù)δ如下：δ(q0,a)=(q0,R),δ(q0,b)=(q1,R),δ(q1,a)=(q1,R),δ(q1,b)=(q2,L),δ(q2,a)=(q0,R),δ(q2,b)=(q2,L),則當(dāng)輸入字符串序列babaa時(shí)，其格局序列為：

q0babaababq1aa

此時(shí)，讀完所有字符并進(jìn)入q1狀態(tài)，且q1∈F是結(jié)束狀態(tài)，故知字符串babaa被M所接受。bq1abaabaq1baabq2abaabaq0baababaq1ababaaq1二、有輸出的有限自動(dòng)機(jī)

有輸出的自動(dòng)機(jī)是有限自動(dòng)機(jī)的另一種類型，這類自動(dòng)機(jī)當(dāng)有字符輸入時(shí)不僅有狀態(tài)轉(zhuǎn)換，同時(shí)會(huì)引起字符的輸出。常見的有輸出的自動(dòng)機(jī)有米蘭機(jī)和摩爾機(jī)。米蘭機(jī)：輸出字符不僅與它所處的狀態(tài)有關(guān)，而且還與輸入字符有關(guān)。摩爾機(jī)：輸出字符僅與它所處的狀態(tài)有關(guān)，而與輸入字符無關(guān)。二、有輸出的有限自動(dòng)機(jī)1.米蘭機(jī)的形式定義定義：設(shè)有限自動(dòng)機(jī)M為一個(gè)六元組,M=(Q,T,R,δ,g,q0),其中：(1)Q是有限狀態(tài)集合;則稱M為米蘭機(jī)。(2)T是有限輸入字母表

;(3)R是有限輸出字母表

;(4)δ是狀態(tài)轉(zhuǎn)換函數(shù)，是從Q×T到Q的映射；(5)g是輸出函數(shù)，是從Q×T到R的映射；(6)q0是初始狀態(tài)，q0∈Q；注意：米蘭機(jī)無所謂終止?fàn)顟B(tài)，它的任務(wù)主要是要得到輸出字符串二、有輸出的有限自動(dòng)機(jī)2.

米蘭機(jī)工作狀況的描述可以使用狀態(tài)轉(zhuǎn)換函數(shù)δ和輸出函數(shù)g來描述米蘭機(jī)工作狀況的瞬時(shí)變化。例如：當(dāng)轉(zhuǎn)換函數(shù)為δ(q,a)=p時(shí)，表明在狀態(tài)q，輸入字符為a時(shí)，M轉(zhuǎn)換到狀態(tài)p，此時(shí)g(q,a)=b表示輸出字符b。用狀態(tài)圖表示這個(gè)工作狀況，則是從q到p有一條標(biāo)有a/b的弧，a是輸入字符，b是輸出字符。輸出字符b依賴于當(dāng)前狀態(tài)q和當(dāng)前的輸入字符aqpa/b二、有輸出的有限自動(dòng)機(jī)3.

米蘭機(jī)的應(yīng)用舉例例1：設(shè)計(jì)一個(gè)米蘭機(jī)M=(Q,T,R,δ,g,q0),它的輸出是輸入字符個(gè)數(shù)的模3值。

②由于任何正整數(shù)對(duì)3的模運(yùn)算的結(jié)果只可能是：0,1,2，所以輸出字母表R設(shè)為{0,1,2}；解：

①由于輸出僅與輸入字符的個(gè)數(shù)有關(guān)，故可設(shè)輸入字母表T只有一個(gè)字符a；

④根據(jù)題意，狀態(tài)轉(zhuǎn)換函數(shù)δ和輸出函數(shù)g定義如下：

δ(q0,a)=q1δ(q1,a)=q2

δ(q2,a)=q0

g(q0,a)=1

g(q1,a)=2g(q2,a)=0

③由于M要記住當(dāng)前已經(jīng)輸入的字符個(gè)數(shù)的模3值，故可設(shè)3個(gè)不同狀態(tài)q0,q1,q2來記憶這3種不同狀態(tài)。例1：設(shè)計(jì)一個(gè)米蘭機(jī)M=(Q,T,R,δ,g,q0),它的輸出是輸入字符個(gè)數(shù)的模3值。

②由于任何正整數(shù)對(duì)3的模運(yùn)算的結(jié)果只可能是：0,1,2，所以輸出字母表R設(shè)為{0,1,2}；解：

①由于輸出僅與輸入字符的個(gè)數(shù)有關(guān)，故可設(shè)輸入字母表T只有一個(gè)字符a；

④根據(jù)題意，狀態(tài)轉(zhuǎn)換函數(shù)δ和輸出函數(shù)g定義如下：

δ(q0,a)=q1δ(q1,a)=q2

δ(q2,a)=q0

g(q0,a)=1

g(q1,a)=2g(q2,a)=0

③由于M要記住當(dāng)前已經(jīng)輸入的字符個(gè)數(shù)的模3值，故可設(shè)3個(gè)不同狀態(tài)q0,q1,q2來記憶這3種不同狀態(tài)。例1：設(shè)計(jì)一個(gè)米蘭機(jī)M=(Q,T,R,δ,g,q0),它的輸出是輸入字符個(gè)數(shù)的模3值。

②由于任何正整數(shù)對(duì)3的模運(yùn)算的結(jié)果只可能是：0,1,2，所以輸出字母表R設(shè)為{0,1,2}；解：

①由于輸出僅與輸入字符的個(gè)數(shù)有關(guān)，故可設(shè)輸入字母表T只有一個(gè)字符a；

④根據(jù)題意，狀態(tài)轉(zhuǎn)換函數(shù)δ和輸出函數(shù)g定義如下：

δ(q0,a)=q1δ(q1,a)=q2

δ(q2,a)=q0

g(q0,a)=1

g(q1,a)=2g(q2,a)=0

③由于M要記住當(dāng)前已經(jīng)輸入的字符個(gè)數(shù)的模3值，故可設(shè)3個(gè)不同狀態(tài)q0,q1,q2來記憶這3種不同狀態(tài)。故Q={q0,q1,q2}故有：M=({q0,q1,q2},{a},{0,1,2},δ,g,q0)其轉(zhuǎn)換圖如右所示：q0q1q2a/1a/2a/0當(dāng)輸入字符串為aaaaa時(shí)，M的動(dòng)作為：q0→q1→q2→q0→q1→q2,輸出字符串為:12012狀態(tài)序列為:q0q1q2q0q1q2a/1a/2a/0a/1a/2二、有輸出的有限自動(dòng)機(jī)4.摩爾機(jī)的形式定義定義：設(shè)有限自動(dòng)機(jī)M為一個(gè)六元組,M=(Q,T,R,δ,g,q0),其中：(1)Q是有限狀態(tài)集合;則稱M為摩爾機(jī)。(2)T是有限輸入字母表

;(3)R是有限輸出字母表

;(4)δ是狀態(tài)轉(zhuǎn)換函數(shù)，是從Q×T到Q的映射；(5)g是輸出函數(shù)，是從Q到R的映射；(6)q0是初始狀態(tài)，q0∈Q；注意：摩爾機(jī)也無所謂終止?fàn)顟B(tài)，它的任務(wù)主要也是要得到一個(gè)輸出字符串。二、有輸出的有限自動(dòng)機(jī)5.

摩爾機(jī)工作狀況的描述與米蘭機(jī)一樣，可以使用狀態(tài)轉(zhuǎn)換函數(shù)δ和輸出函數(shù)g來描述摩爾機(jī)工作狀況的瞬時(shí)變化。例如：當(dāng)轉(zhuǎn)換函數(shù)為δ(q,a)=p時(shí)，表明在狀態(tài)q，輸入字符為a時(shí)，M轉(zhuǎn)換到狀態(tài)p，此時(shí)g(p)=b表示當(dāng)達(dá)到狀態(tài)p時(shí)輸出字符b。用狀態(tài)圖表示這個(gè)工作狀況，則是從q到p有一條標(biāo)有a的弧，而各狀態(tài)中的字符（如b1或b2）則表示達(dá)到該狀態(tài)時(shí)M的輸出字符。輸出字符b僅依賴于當(dāng)前狀態(tài)p。q,b1p,b2ax1x2x3x4二、有輸出的有限自動(dòng)機(jī)6.

摩爾機(jī)的應(yīng)用舉例例1：設(shè)計(jì)一個(gè)摩爾機(jī)M=(Q,T,R,δ,g,q0),它的輸入字符串w是0,1組成的；輸出值是w中1的個(gè)數(shù)減0的個(gè)數(shù)的模4值。

②由于任何正整數(shù)對(duì)4的模運(yùn)算的結(jié)果只可能是：0,1,2,3,所以輸出字母表R設(shè)為{0,1,2,3}；解：①由于輸入字符為0或1，故可設(shè)輸入字母表T為{0,1}；

④根據(jù)題意，狀態(tài)轉(zhuǎn)換函數(shù)δ和輸出函數(shù)g定義如下：

δ(q0,0)=q3δ(q1,0)=q0

δ(q2,0)=q1δ(q3,0)=q2

g(q0)=0

g(q1)=1g(q2)=2g(q3)=3

③由于M要記住的當(dāng)前已經(jīng)輸入的1的個(gè)數(shù)和0的個(gè)數(shù)的差的模4值，故可設(shè)4個(gè)不同狀態(tài)q0,q1,q2,q3來記憶這4種不同狀態(tài)。

δ(q0,1)=q1δ(q1,1)=q2

δ(q2,1)=q3δ(q3,1)=q0例1：設(shè)計(jì)一個(gè)摩爾機(jī)M=(Q,T,R,δ,g,q0),它的輸入字符串w是0,1組成的；輸出值是w中1的個(gè)數(shù)減0的個(gè)數(shù)的模4值。

②由于任何正整數(shù)對(duì)4的模運(yùn)算的結(jié)果只可能是：0,1,2,3,所以輸出字母表R設(shè)為{0,1,2,3}；解：①由于輸入字符為0或1，故可設(shè)輸入字母表T為{0,1}；

④根據(jù)題意，狀態(tài)轉(zhuǎn)換函數(shù)δ和輸出函數(shù)g定義如下：

δ(q0,0)=q3δ(q1,0)=q0

δ(q2,0)=q1δ(q3,0)=q2

g(q0)=0

g(q1)=1g(q2)=2g(q3)=3

③由于M要記住的當(dāng)前已經(jīng)輸入的1的個(gè)數(shù)和0的個(gè)數(shù)的差的模4值，故可設(shè)4個(gè)不同狀態(tài)q0,q1,q2,q3來記憶這4種不同狀態(tài)。

δ(q0,1)=q1δ(q1,1)=q2

δ(q2,1)=q3δ(q3,1)=q0例1：設(shè)計(jì)一個(gè)摩爾機(jī)M=(Q,T,R,δ,g,q0),它的輸入字符串w是0,1組成的；輸出值是w中1的個(gè)數(shù)減0的個(gè)數(shù)的模4值。

②由于任何正整數(shù)對(duì)4的模運(yùn)算的結(jié)果只可能是：0,1,2,3,所以輸出字母表R設(shè)為{0,1,2,3}；解：①由于輸入字符為0或1，故可設(shè)輸入字母表T為{0,1}；

④根據(jù)題意，狀態(tài)轉(zhuǎn)換函數(shù)δ和輸出函數(shù)g定義如下：

δ(q0,0)=q3δ(q1,0)=q0

δ(q2,0)=q1δ(q3,0)=q2

g(q0)=0

g(q1)=1g(q2)=2g(q3)=3

③由于M要記住的當(dāng)前已經(jīng)輸入的1的個(gè)數(shù)和0的個(gè)數(shù)的差的模4值，故可設(shè)4個(gè)不同狀態(tài)q0,q1,q2,q3來記憶這4種不同狀態(tài)。

δ(q0,1)=q1δ(q1,1)=q2

δ(q2,1)=q3δ(q3,1)=q0

②由于任何正整數(shù)對(duì)4的模運(yùn)算的結(jié)果只可能是：0,1,2,3,所以輸出字母表R設(shè)為{0,1,2,3}；解：①由于輸入字符為0或1，故可設(shè)輸入字母表T為{0,1}；

④根據(jù)題意，狀態(tài)轉(zhuǎn)換函數(shù)δ和輸出函數(shù)g定義如下：

δ(q0,0)=q3δ(q1,0)=q0

δ(q2,0)=q1δ(q3,0)=q2

g(q0)=0

g(q1)=1g(q2)=2g(q3)=3

③由于M要記住的當(dāng)前已經(jīng)輸入的1的