计算理论导引

1计算理论第1章正则语言2复习:确定型有穷自动机的形式定义定义1.1有穷自动机是一个5

元组(Q,

,

,q0,F)，其中(1)Q是一个有穷集合，称为状态集。(2)

是一个有穷集合，称为字母表。(3)

:QQ是转移函数。(4)q0Q是起始状态。(5)FQ是接受状态集。3复习:非确定性非确定性体现在

转换规则——一入多出,

是空字——无入转态q2q1q311q1q2

4复习:非确定型有穷自动机的形式定义定义1.17非确定型有穷自动机(NFA)是一个5

元组(Q,

,

,q0,F)，其中(1)Q是有穷的状态集。(2)

是有穷的字母表。(3)

:Q

ε

P(Q)是转移函数。(4)q0Q是起始状态。(5)FQ是接受状态集。5复习:等价性定理1.28一个语言是正则的，当且仅当可以用正则表达式描述它。定理1.19每一台非确定型有穷自动机都等价于某一台确定型有穷自动机。6复习:正则表达式转换成NFA例1.30

把正则表达式(ab∪a)*

转换成一台NFA。(1)a(5)(ab∪a)*(2)b(3)ababa

(4)ab∪a

7主要内容2.1有穷自动机2.2非确定性2.3正则表达式2.4非正则语言

本章小结

作业8非正则语言对于如下的语言，是否能找到识别该语言的DFA？B={0n1n|n≥0}C={w|w中0和1的个数相等}D={w|w中01和10作为子串出现的次数相同}9泵引理(pumpinglemma)

定理1.37若A是一个正则语言，则存在一个数p

(泵长度)使得，如果s是A中任一长度不小于p的字符串，那么s可以被分成3段，s=xyz，满足下述条件：对于每一个i

0,xyiz∈A

(2)|

y

|

0(3)|

xy

|≤p我们总能够在离s

的开始处不太远的地方找到一个非空的串y，然后可以把它看作一个“泵”，重复y

任意多次，或者去掉它，而所得到的结果串仍然属于A。10非正则语言q0qmqk11泵引理的证明设M=(Q,,,q1,F)是一台识别A的DFA，并设p是M的状态数。设s=s1s2…sn

是A中长度为n的字符串，这里n≥p。又设r1,r2,…,rn+1是M在处理s的过程中进入的状态序列，因而ri+1=(ri,si)，1≤i≤n。该序列的长度为n+1，不小于p+1。根据鸽巢原理，在该序列的前p+1个元素中，一定有两个相同的状态。设第1个是rj，第2个是rl。由于rl出现在序列的前p+1个位置中，而且序列是从r1开始的，故有l

≤p+1。此时，令x=s1…sj-1，y=sj…sl-1，z=sl…sn。12泵引理的证明由于x把M从r1带到rj,y把M从rj

带到rj，z把M从rj带到rn+1，而rn+1是一个接受状态，故对于i≥0，M接受xyiz。已知j≠

l，故|y|>0，又已知l

≤p+1，故|xy|≤

p。于是，满足泵引理的3个条件。13泵引理的应用例1.38

设B={0n1n|n≥0}。用泵引理证明B不是正则的。假设B是正则的，令p是由泵引理给出的泵长度。选择s=0p1p，按照泵引理所述，可令s=xyz

根据泵引理，有|

xy

|≤p，因此y=0k，k≥1此时有x=0p-k-j,z=0j1p从而有xyiz=0p-k-j(0k)i0j1p

=0p+(i-1)k1p

当i=2时，我们有：

xy2z=0p+(2-1)k1p=0p+k1p注意到k≥1，所以，p+k>p。这就是说，0p+k1p

B这与泵引理矛盾。所以，B不是正则的。14泵引理的应用并不是所有满足泵引理的语言都是正则语言。就是这样的一个例子，它满足泵引理，但并不是正则语言。15本章小结有穷自动机DFAM=(Q,,,q0,F