計算理論導引

計算理論1復習:有窮自動機的形式定義定義1.12有窮自動機是一個5

元組(Q,S,d,q0,F

)，其中Q

是一個有窮集合，稱為狀態(tài)集。S

是一個有窮集合，稱為字母表。d

:Q·Sfi

Q是轉移函數(shù)。q0?Q

是起始狀態(tài)。F?Q

是接受狀態(tài)集。復習:計算的形式化定義設M

=(Q,S,d,q0,F)是一臺有窮自動機，w

=w1w2…wn

是一個字符串，并且wi

是字母表S

的成員。如果存在Q

中的狀態(tài)序列r0,r1,…,rn，滿足下列條件：r0

=

q0d

(ri

,

wi+1)

=

ri+1

,

i

=

0,

1,

…,

n–1rn

?

F則M

接受w。定義如果一個語言被一臺有窮自動機識別，則稱它是正則1.7

語言。3復習:設計有窮自動機例：設計有窮自動機E1，假設字母表是{0,1}，識別的語言由所有含有奇數(shù)個1

的字符串組成。qoddqeven10104識別的語言由所有含有偶數(shù)個1

的字符串組成？復習:設計有窮自動機例

設計有窮自動機

E2，使其能識別含有

001作為子串組成的正則語言。q001qq0q000150100,11識別不含有001

作為子串組成的正則語言？正則運算定義

設A

和

B

是兩個語言，定義正則運算并、連接和星號1.10

如下：并：

A∪B

=

{

x

|

x∈A

或

x∈B

}連接：A B

=

{

xy

|

x∈A

且

y∈B

}星號：A*={x1x2…xk

|

k

≥0

且每一個xi

∈A}6正則運算定理1.127F={(r1,r2)|

r1?F1

或r2?F2}正則語言類在并運算下封閉。如果A1和A2是正則語言，則A1∪A2也是正則語言。設M1

識別A1，M2

識別A2。并設M1=(Q1,S,d1,q1,F1)

和M2=(Q2,S,d2,q2,F2)(例子？)構造識別A1∪A2

的M=(Q,S,d,q0,F)Q=Q1·Q2

={(r1,r2)|

r1?Q1

且r2?Q2}d((r1,r2),a

)=(d1(r1,a),

d2(r2,a))q0

=

(q1,q2)正則運算定理1.138正則語言類在連接運算下封閉。證明思路

按照定理1.12證明思路試一下。輸入：M1接受第一段且M2

接受第二段時，M才接受；？M不知道在什么地方將它的輸入分開（什么地方第一段結束，第二段開始)主要內容9有窮自動機非確定性正則表達式非正則語言本章小結作業(yè)非確定性非確定性體現(xiàn)在轉換規(guī)則——一入多出,e是空字——無入轉態(tài)q2q1q311q1q2e1011非確定性q1,q2不確定性表現(xiàn)：q11

Y?

Y有兩個可能狀態(tài):e

導致q2

自動漂移到q3是否接受“0110”和”1”0110——q1

fi

q1

fi

q2

fi

q3

fi

q4

fi

q41——{q1,

q2

,q3}10,

e0,11q4q1q2q30,1非確定性例1.14

設A是{0,

1}上倒數(shù)第三個符號為1

的所有字符串組成的語言，構造非確定性自動機。0,11q4q1q2q30,10,112非確定性例1.15

考慮圖示的NFA

N

，它的輸入字母表{0}由一個符號組成。只含一個符號的字母表稱為一元字母表。考慮它接受的語言。e0e000130非確定性例1.16

考慮圖示的NFA

N

。運行這臺機器，判斷其是否識別ε、a、baba、baa、b、bb、babba。aa,

bbq1q2q3a14e非確定型有窮自動機的形式定義定義1.1715非確定型有窮自動機(NFA)是一個5

元組(Q,S,d,q0,F

)，其中Q

是有窮的狀態(tài)集。S

是有窮的字母表。d

:Q·Sεfi

P(Q)是轉移函數(shù)。q0?Q

是起始狀態(tài)。F?Q

是接受狀態(tài)集。NFA

的形式化描述舉例例1.18

給出圖示的NFA

的形式化描述。1

0,

e1q1

q2

q3

q40,1

0,116NFA

計算的形式化定義17設N

=(Q,S,d,q0,F)是一臺NFA，w

=w1w2…wn

是一個字符串，并且wi

是字母表S

e

的成員。如果存在Q中的狀態(tài)序列r0,r1,…,rn，滿足下列條件：r0

=

q0ri+1

?

d

(ri

,

wi+1) ,

i

=

0,

1,

…,

n–1rn

?

F則N

接受w。NFA與DFA的等價性定理1.19每一臺非確定型有窮自動機都等價于某一臺確定型有窮自動機。q11

q2q3q511{q1}

→

{q2,

q3,

q5}q2q3q51q411

112q03

q13q1

,q4q03q2

,q3

,q5q5

181219NFA與DFA的等價性定理1.19每一臺非確定型有窮自動機都等價于某一臺確定型有窮自動機。設N

=(Q,S,d,q0,F)是識別語言A

的NFA。假設N

沒有e箭頭。構造識別A

的DFA

M=(Q￠,S,d

￠,q0￠,F

￠)Q￠=P(Q)對于R?Q￠和a?

S，令d

￠(R,a)={

q?Q

|

存在r?

R,使得q?

d(r,a)}q0￠={

q0

}F￠={R?Q￠|

R

包含N

的一個接受狀態(tài)}NFA與DFA的等價性定理1.1920每一臺非確定型有窮自動機都等價于某一臺確定型有窮自動機?？紤]N

有e箭頭。對于M的任意一個狀態(tài)R，定義E(R)為從R出發(fā)只沿著e箭頭可以達到的狀態(tài)集合，包括R

本身的所有成員在內。

E(R)={q

|

從R出發(fā)沿著0

或多個e箭頭可以到達q}修改M

的轉移函數(shù)d

￠(R,a)={

q?Q

|

存在r?

R,使得q?

E(d(r,a))}

q0￠=E({q0})NFA與DFA的等價性推論1.2021一個語言是正則的，當且僅當有一臺非確定型有窮自動機識別它。NFA

轉換成等價的DFA

舉例例1.21

將圖示的NFA

N

轉換成等價的DFA。aa,

bb123aeQ

={

?

,

{1},

{2},

{3},

{1,2},

{1,3},

{2,3},

{1,2,3}

}E({1})

=

{

1,

3

}F

=

{{1},

{1,2},

{1,3},

{1,2,3}}考察{{2},{1},{3},{1,2},{2,3},

{1,2,3},

?

,{1,3}}{1}?{1,2}{2}a{3}{1,2,3}{2,3}bababa,ba{1,

3}baba,bab22在正則運算下的封閉性定理1.22正則語言類在并運算下封閉。N23N2N1eefq

=q0且a

?e2

2{q1,q2}

q

=q0且a

=ed

(q,a)

q

?

Qd(q,

a)

=

設1

1

1

1

1N

=

(Q

,

S,

d

,

q

,

F

)N2

=

(Q2,

S,

d2,

q2,

F2)構造

N

=

(Q,

S,

d,

q0,F)d1

(q,a)

q

?

Q1NFA與DFA的等價性定理1.23正則語言類在連接運算下封閉。N24N2N1eeNFA與DFA的等價性定理1.24正則語言類在星運算下封閉(注意應接受空串)。N25N1eee