计算理论导引

计算理论1复习:有穷自动机的形式定义定义1.12有穷自动机是一个5

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

)，其中Q

是一个有穷集合，称为状态集。S

是一个有穷集合，称为字母表。d

:Q·Sfi

Q是转移函数。q0˛Q

是起始状态。F˝Q

是接受状态集。复习:计算的形式化定义设M

=(Q,S,d,q0,F)是一台有穷自动机，w

=w1w2…wn

是一个字符串，并且wi

是字母表S

的成员。如果存在Q

中的状态序列r0,r1,…,rn，满足下列条件：r0

=

q0d

(ri

,

wi+1)

=

ri+1

,

i

=

0,

1,

…,

n–1rn

˛

F则M

接受w。定义如果一个语言被一台有穷自动机识别，则称它是正则1.7

语言。3复习:设计有穷自动机例：设计有穷自动机E1，假设字母表是{0,1}，识别的语言由所有含有奇数个1

的字符串组成。qoddqeven10104识别的语言由所有含有偶数个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有穷自动机非确定性正则表达式非正则语言本章小结作业非确定性非确定性体现在转换规则——一入多出,e是空字——无入转态q2q1q311q1q2e1011非确定性q1,q2不确定性表现：q11

Y?

Y有两个可能状态: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}上倒数第三个符号为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

是有穷的状态集。S

是有穷的字母表。d

:Q·Sεfi

P(Q)是转移函数。q0˛Q

是起始状态。F˝Q

是接受状态集。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中的状态序列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

的一个接受状态}NFA与DFA的等价性定理1.1920每一台非确定型有穷自动机都等价于某一台确定型有穷自动机。考虑N

有e箭头。对于M的任意一个状态R，定义E(R)为从R出发只沿着e箭头可以达到的状态集合，包括R

本身的所有成员在内。

E(R)={q

|

从R出发沿着0

或多个e箭头可以到达q}修改M

的转移函数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