計算理論導(dǎo)引

1計算理論第1章正則語言2復(fù)習(xí):確定型有窮自動機的形式定義定義1.1有窮自動機是一個5

元組(Q,

,

,q0,F)，其中(1)Q是一個有窮集合，稱為狀態(tài)集。(2)

是一個有窮集合，稱為字母表。(3)

:QQ是轉(zhuǎn)移函數(shù)。(4)q0Q是起始狀態(tài)。(5)FQ是接受狀態(tài)集。3復(fù)習(xí):非確定性非確定性體現(xiàn)在

轉(zhuǎn)換規(guī)則——一入多出,

是空字——無入轉(zhuǎn)態(tài)q2q1q311q1q2

4復(fù)習(xí):非確定型有窮自動機的形式定義定義1.17非確定型有窮自動機(NFA)是一個5

元組(Q,

,

,q0,F)，其中(1)Q是有窮的狀態(tài)集。(2)

是有窮的字母表。(3)

:Q

ε

P(Q)是轉(zhuǎn)移函數(shù)。(4)q0Q是起始狀態(tài)。(5)FQ是接受狀態(tài)集。5復(fù)習(xí):等價性定理1.28一個語言是正則的，當(dāng)且僅當(dāng)可以用正則表達式描述它。定理1.19每一臺非確定型有窮自動機都等價于某一臺確定型有窮自動機。6復(fù)習(xí):正則表達式轉(zhuǎn)換成NFA例1.30

把正則表達式(ab∪a)*

轉(zhuǎn)換成一臺NFA。(1)a(5)(ab∪a)*(2)b(3)ababa

(4)ab∪a

7主要內(nèi)容2.1有窮自動機2.2非確定性2.3正則表達式2.4非正則語言

本章小結(jié)

作業(yè)8非正則語言對于如下的語言，是否能找到識別該語言的DFA？B={0n1n|n≥0}C={w|w中0和1的個數(shù)相等}D={w|w中01和10作為子串出現(xiàn)的次數(shù)相同}9泵引理(pumpinglemma)

定理1.37若A是一個正則語言，則存在一個數(shù)p

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

0,xyiz∈A

(2)|

y

|

0(3)|

xy

|≤p我們總能夠在離s

的開始處不太遠的地方找到一個非空的串y，然后可以把它看作一個“泵”，重復(fù)y

任意多次，或者去掉它，而所得到的結(jié)果串仍然屬于A。10非正則語言q0qmqk11泵引理的證明設(shè)M=(Q,,,q1,F)是一臺識別A的DFA，并設(shè)p是M的狀態(tài)數(shù)。設(shè)s=s1s2…sn

是A中長度為n的字符串，這里n≥p。又設(shè)r1,r2,…,rn+1是M在處理s的過程中進入的狀態(tài)序列，因而ri+1=(ri,si)，1≤i≤n。該序列的長度為n+1，不小于p+1。根據(jù)鴿巢原理，在該序列的前p+1個元素中，一定有兩個相同的狀態(tài)。設(shè)第1個是rj，第2個是rl。由于rl出現(xiàn)在序列的前p+1個位置中，而且序列是從r1開始的，故有l(wèi)

≤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是一個接受狀態(tài)，故對于i≥0，M接受xyiz。已知j≠

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

≤p+1，故|xy|≤

p。于是，滿足泵引理的3個條件。13泵引理的應(yīng)用例1.38

設(shè)B={0n1n|n≥0}。用泵引理證明B不是正則的。假設(shè)B是正則的，令p是由泵引理給出的泵長度。選擇s=0p1p，按照泵引理所述，可令s=xyz

根據(jù)泵引理，有|

xy

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

=0p+(i-1)k1p

當(dāng)i=2時，我們有：

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

B這與泵引理矛盾。所以，B不是正則的。14泵引理的應(yīng)用并不是所有滿足泵引理的語言都是正則語言。就是這樣的一個例子，它滿足泵引理，但并不是正則語言。15本章小結(jié)有窮自動機DFAM=(Q,,,q0,F