第4章正則語言的性質(zhì)

1、1第第4章章 正則語言的性質(zhì)正則語言的性質(zhì) 2一、正則語言的封閉性質(zhì)定義定義4.1 如果屬于某一語言類的任何語言在某一特定運算下所如果屬于某一語言類的任何語言在某一特定運算下所得的結(jié)果仍然是該類語言，則稱該語言類對此運算是封閉的，得的結(jié)果仍然是該類語言，則稱該語言類對此運算是封閉的，并稱該語言類對此運算具有封閉性（并稱該語言類對此運算具有封閉性（closure property）。）。 給定正則語言給定正則語言L1和和L2，它們的并集、交集、連接是否仍然是正，它們的并集、交集、連接是否仍然是正則語言？則語言？ 定理定理4.1 如果如果L1和和L2是正則語言，那么是正則語言，那么L1L2也是正則

2、語言。也是正則語言。證明：如果證明：如果L1和和L2是正則的，那么一定存在正則表達式是正則的，那么一定存在正則表達式r1和和r2，使得使得L1L（r1），），L2L（r2）。根據(jù)定義，）。根據(jù)定義，r1+r2是表示語言是表示語言L1L2的正則表達式。因此，正則語言對于并運算是封閉的。的正則表達式。因此，正則語言對于并運算是封閉的。3定理定理4.2 如果如果L是字母表是字母表 上的正則語言，則上的正則語言，則L= *-L是正則是正則語言。語言。證明：如果證明：如果L是正則的，設接受是正則的，設接受L的的DFA為為M（Q， ， ，q0，F(xiàn)）。）。下面構(gòu)造下面構(gòu)造DFA M：取取M與與M的終結(jié)狀態(tài)集

3、互為補集，除了終結(jié)狀態(tài)集為的終結(jié)狀態(tài)集互為補集，除了終結(jié)狀態(tài)集為Q-F外，外，M的其余結(jié)構(gòu)都與的其余結(jié)構(gòu)都與M相同，即相同，即 M(Q， ， ，q0，Q-F）顯然，對于顯然，對于M接受的串，接受的串，M將不接受，對于將不接受，對于M接受的串，接受的串，M將不接受。因此將不接受。因此L（M）= *-L 所以所以 *-L是正則語言。是正則語言。4例例1 設設DFA M如圖所示如圖所示q0Start011001q2q1 它接受的語言為它接受的語言為L=w01| w 0，1* ，即接受所有以，即接受所有以01結(jié)尾的結(jié)尾的0和和1組成的串，組成的串，用正則表達式的形式描述就是用正則表達式的形式描述就是L

4、（M）=（0+1）*01 *-L就是所有不以就是所有不以01結(jié)尾的由結(jié)尾的由0和和1組成的串。組成的串。右圖給出了右圖給出了 *-L （M）的自動機，的自動機，它把上圖中的終結(jié)狀態(tài)變?yōu)榉撬焉蠄D中的終結(jié)狀態(tài)變?yōu)榉墙K結(jié)狀態(tài)，非終結(jié)狀態(tài)變?yōu)榻K終結(jié)狀態(tài)，非終結(jié)狀態(tài)變?yōu)榻K結(jié)狀態(tài)。結(jié)狀態(tài)。q2Start011001q1q05 定理定理4.3 如果如果L1和和L2是正則語言，則是正則語言，則L1L2是正則語言。是正則語言。證明：證明：用構(gòu)造證明的方法：用構(gòu)造證明的方法：設設L1L（M1），），L2L（M2），），其中其中DFA M1（Q1， ， 1，q0，F(xiàn)1），）， DFA M2（Q2， ， 2，p0，

5、F2），），構(gòu)造構(gòu)造DFA M=（Q1 Q2， ， ，F(xiàn)1 F2） ，其中其中：（：（Q1 Q2）Q1 Q2對對 p1 Q1，p2 Q2，a （，a）=，由定義可以看出，由定義可以看出，w被被M接受當且僅當接受當且僅當w同時被同時被M1和和M2接接受，因此，受，因此，L1L2是正則的。是正則的。6例例2 設有如圖下的兩個設有如圖下的兩個DFA，M1接受所有包含接受所有包含0的串，的串，M2接受所有包含接受所有包含1的串，的串，Startp01q0, 1a）Startr10s0, 1b）Startqspr1psqr10010, 10按定理4.3的構(gòu)造方法，構(gòu)造出的DFA M如右圖所示,M接受的同

6、時含有0和1的串。7定理定理4.4 如果如果L1和和L2是正則語言，那么是正則語言，那么L1-L2也是正則語言。也是正則語言。證明：證明：根據(jù)集合差運算的定義有根據(jù)集合差運算的定義有 L1-L2= L1L2如果如果L1和和L2是正則的，根據(jù)定理是正則的，根據(jù)定理4.2，L2是正則的，是正則的，再由定理再由定理4.3，L1L2也是正則的。所以，正則語言在差運算也是正則的。所以，正則語言在差運算上是封閉的。上是封閉的。定理定理4.5 如果如果L1和和L2是正則語言，那么是正則語言，那么L1L2和和L1*也都是正則語也都是正則語言。言。證明：證明：如果如果L1和和L2是正則的，那么一定存在正則表達式

7、是正則的，那么一定存在正則表達式r1和和r2，使得，使得L1L（r1），），L2L（r2）。根據(jù)正則表達式的定義，）。根據(jù)正則表達式的定義，r1r2和和r1*分別是表示語言分別是表示語言L1L2和和L1*的正則表達式。因此，正則的正則表達式。因此，正則語言在連接和星閉包運算上都是封閉的。語言在連接和星閉包運算上都是封閉的。8定理定理4.6 如果如果L是正則語言，則是正則語言，則L的逆的逆LR= w| wT L（wT表示表示w的倒序）也是正則語言。的倒序）也是正則語言。 證明：證明：證法證法1（用構(gòu)造自動機的方法）（用構(gòu)造自動機的方法）假設假設L是正則語言，是正則語言， M是接受是接受L的自動機

8、，通過下面方法構(gòu)的自動機，通過下面方法構(gòu)造一個接受造一個接受LR的自動機的自動機M：（1）M中的弧是中的弧是M中所有弧的方向反轉(zhuǎn)構(gòu)成；中所有弧的方向反轉(zhuǎn)構(gòu)成；（2）M的終結(jié)狀態(tài)是的終結(jié)狀態(tài)是M的初始狀態(tài)；的初始狀態(tài)；（3）如果）如果M不止一個終結(jié)狀態(tài)，則在不止一個終結(jié)狀態(tài)，則在M中創(chuàng)建一個新的初中創(chuàng)建一個新的初始狀態(tài)，從該狀態(tài)出發(fā)到始狀態(tài)，從該狀態(tài)出發(fā)到M的所有終結(jié)狀態(tài)都建立一個的所有終結(jié)狀態(tài)都建立一個 轉(zhuǎn)轉(zhuǎn)移。移。修改后的修改后的NFA M接受接受wT，當且僅當，當且僅當M接受接受w。因此，。因此，M接接受受LR，從而證明了逆運算的封閉性。，從而證明了逆運算的封閉性。9證法證法2:設設L由正

9、則表達式由正則表達式r定義，對定義，對r的構(gòu)造次數(shù)進行歸納證明：的構(gòu)造次數(shù)進行歸納證明：（1）設）設r的構(gòu)造次數(shù)為的構(gòu)造次數(shù)為0，即，即r是是， 或者或者a,則則R=， R= ，a R= a，此時，此時rR和和r相同。相同。（2）設定理在）設定理在r的構(gòu)造次數(shù)小于的構(gòu)造次數(shù)小于k時成立，討論時成立，討論r的構(gòu)造次數(shù)的構(gòu)造次數(shù)等于等于k時，時，情況情況 設設r=r1+r2，其中，其中r1和和r2的構(gòu)造次數(shù)都小于的構(gòu)造次數(shù)都小于k，由歸納假設，可以構(gòu)造由歸納假設，可以構(gòu)造r1R和和r2R，使得，使得L(r1R)=L(r1)R，L(r2R)=L(r2)R，因為因為L(r)=L(r1) L(r2)，所

10、以，所以L(r)R=L(r1)R L(r2)R，因此因此r1R + r2R就是代表就是代表L(r)R的正則表達式。的正則表達式。情況情況 設設r=r1r2，其中，其中r1和和r2的構(gòu)造次數(shù)都小于的構(gòu)造次數(shù)都小于k，由歸納假設，可以構(gòu)造由歸納假設，可以構(gòu)造r1R和和r2R，使得，使得L(r1R)=L(r1)R，L(r2R)= L(r2)R，由于由于L(r)=L(r1)L(r2)，因此，因此L(r)R=L(r1)R L(r2)R，所以，所以r1Rr2R就是就是代表代表L(r)R的正則表達式。的正則表達式。10情況情況 設設r=r1*，其中，其中r1的構(gòu)造次數(shù)小于的構(gòu)造次數(shù)小于k，由歸納假設，可以構(gòu)

11、造由歸納假設，可以構(gòu)造r1R，使得，使得L（r1R）= L（r1）R，因為因為L（r）= L（r1）*，對于對于 w L（r），），w=w1w2wm，每個，每個wi L（r1）。）。wR= wmRwm-1Rw1R，其中每個，其中每個wiR L（r1）R，因此因此wR L（r1 R）*）。）。反之，反之， w L（r1 R）*），），w都有都有w1w2wn的形式，的形式，其中其中wi L（r1）R。因此，因此，wR= wnRwn-1Rw1R L（r1*）=L(r),因此（因此（r1 R）*就是代表就是代表L（r）R的正則表達式。的正則表達式。11例例3 設設L是由正則表達式（是由正則表達式（0+

12、1）0*表示的語言，根據(jù)連接規(guī)則表示的語言，根據(jù)連接規(guī)則可知可知LR是（是（0*）R（0+1）R表示的語言，而（表示的語言，而（0*）R=0*，0或或1的反的反轉(zhuǎn)是它自身，轉(zhuǎn)是它自身，即（即（0+1）R=（0+1），因此），因此LR的正則表達式為的正則表達式為0*（0+1）。）。定義定義4.2 假設假設 和和 是兩個字母表。函數(shù)是兩個字母表。函數(shù) h：*如果對于如果對于 x,y，都有，都有h(xy)=h(x)h(y)，則稱則稱h為為 到到 *的同態(tài)映射（的同態(tài)映射（homomorphism）。）。對于對于L*， h（L）=h(x) * 稱為稱為L的同態(tài)像。的同態(tài)像。對于對于w*，h-1（ w）

13、=x|h(x)=w 稱為稱為w的同態(tài)原像。的同態(tài)原像。對于對于L*，h-1（L）=x|h(x) L 稱為稱為L的同態(tài)原像，的同態(tài)原像，并稱并稱h-1（L）為）為L的逆同態(tài)。的逆同態(tài)。12例例4 已知已知 0，1和和 a，b，c，定義，定義h為為 h(0)ab h(1)bcc那么那么h(010)abbccab。L00，010的同態(tài)像為的同態(tài)像為語言語言h(L)abab，abbccab。例例5 已知已知 0，1和和 a，b，c。同態(tài)映射。同態(tài)映射h為為 h(0)dbcc h(1)bbc如果如果L是正則語言，使用正則表達式是正則語言，使用正則表達式 r=(0+1*)1*表示，那么表示，那么 r1=(

14、dbcc+(bbc)*) (bbc)*表示的語言是正則語言表示的語言是正則語言h(L)。13 定理定理4.7 如果如果L是字母表是字母表 上的正則語言，上的正則語言， h是是 到到 上的同態(tài)映射，則上的同態(tài)映射，則h(L)也是也是 上的正則語言。即正則上的正則語言。即正則語言在同態(tài)運算上是封閉的。語言在同態(tài)運算上是封閉的。證明：證明：設設L是用正則表達式是用正則表達式r表示的正則語言。表示的正則語言。用用h(r)表示把表示把r中的每個符號中的每個符號a，用，用h(a)來代替后的來代替后的表達式。表達式。根據(jù)正則表達式的定義，根據(jù)正則表達式的定義，h(r)也是正則表達式。也是正則表達式。下面證明

15、下面證明h(r)定義的語言是定義的語言是h(L)，即即L(h(r)=h(L(r)。對對r的構(gòu)造次數(shù)進行歸納：的構(gòu)造次數(shù)進行歸納：14（1）設）設r的構(gòu)造次數(shù)為的構(gòu)造次數(shù)為0，即，即r是是， 或者或者a,當當r是是或者或者 時，時，L（r）中或者只含空串，或者沒有串，此時）中或者只含空串，或者沒有串，此時L(h(r)=L(r)，所以，所以L(h(r)=h(L(r)。當當r是是a時，時，L(r)=a，所以，所以h(L(r)=h(a )另一方面，另一方面，h(r)是由符號串是由符號串h(a )表示的表示的 上的正則表達式，因此上的正則表達式，因此L(h(r)=h(a)，所以所以L(h(r)=h(L(

16、r)。（2）設定理在）設定理在r的構(gòu)造次數(shù)小于的構(gòu)造次數(shù)小于k時成立，討論時成立，討論r的構(gòu)造次數(shù)等于的構(gòu)造次數(shù)等于k時，時，設設r=r1+r2，其中，其中r1和和r2都是構(gòu)造次數(shù)都小于都是構(gòu)造次數(shù)都小于k的正則表達式，的正則表達式，由同態(tài)的定義，有由同態(tài)的定義，有h(r) =h(r1+r2)= h(r1)+ h(r2)所以所以L(h(r)=L(h(r1)+ h(r2)= L(h(r1) L( h(r2)把把h作用到一個語言上時，相當于把它單獨作用到語言的每一個字符串，作用到一個語言上時，相當于把它單獨作用到語言的每一個字符串，因此因此 h(L(r)= h(L(r1) L(r2)= h(L(r

17、1) h(L(r2)由歸納假設，由歸納假設，L(h(r1)= h(L(r1)， L( h(r2)= h(L(r2)所以，有所以，有L(h(r)=h(L(r)。對于對于r=r1r2，和，和r=r1*，可以類似地證明，可以類似地證明15定理定理4.8 設設 h是字母表是字母表 到到 上的同態(tài)映射，上的同態(tài)映射， L是字母表是字母表 上的正則語言，則上的正則語言，則h-1(L)也是字母表也是字母表 上正則語言。即正上正則語言。即正則語言在逆同態(tài)運算上是封閉的。則語言在逆同態(tài)運算上是封閉的。（證明略）（證明略）定義定義4.3 設設L1和和L2是定義在同一個字母表上的語言，我是定義在同一個字母表上的語言

18、，我們稱們稱 L1/L2x|xy L1對于某個對于某個y L2 為為L1和和L2的的右商右商（right quotient）。）。 由定義可以看出，由定義可以看出， L1和和L2的右商中的符號串可以這樣求的右商中的符號串可以這樣求出：先找出出：先找出L1中所有其后綴屬于中所有其后綴屬于L2的符號串，由每個這的符號串，由每個這樣的符號串去掉后綴后形成的符號串都屬于樣的符號串去掉后綴后形成的符號串都屬于L1/L2。16例例6 設設 L1=anbm：n 1，m 0 ba L2bm：m 1L2中的符號串至少包含一個中的符號串至少包含一個b。因此，先找出。因此，先找出L1中其后綴為中其后綴為bt(t 1

19、)的串，這些串在的串，這些串在anbm：n 1，m 1中，將這些串中，將這些串去掉形為去掉形為bt( t 1)的后綴的后綴,得到得到 L1L2anbm：n 1，m 0 如果如果L1，L2是正則語言，是正則語言，L1L2還是正則的嗎？還是正則的嗎？定理定理4.9 如果如果L1和和L2是正則語言，那么是正則語言，那么L1L2也是正則語言。也是正則語言。即正則語言在右商運算上是封閉的。即正則語言在右商運算上是封閉的。證明：證明：設設M=(Q, , ，q0，F(xiàn)）是）是DFA，且，且L1=L(M)構(gòu)造一個構(gòu)造一個DFA M=(Q, , ，q0，F(xiàn)），），其中其中F=qi| qi Q且且 y L2，使得，

20、使得 （qi，y） F17下面證明下面證明L（M）L1L2，由由L1L2的定義，對的定義，對 x L1L2，一定存在，一定存在y L2，使得使得xy L1，即，即 （q0，xy） F因此，一定存在某個因此，一定存在某個q Q，使得，使得 （q0，x）=q并且并且 （q，y） F因此，根據(jù)構(gòu)造可知因此，根據(jù)構(gòu)造可知q F，并且，并且M接受接受x。 反之，對于反之，對于M接受的任意接受的任意x，我們都有，我們都有 （q0，x）=q F根據(jù)根據(jù)M的構(gòu)造，一定存在一個的構(gòu)造，一定存在一個y L2，滿足滿足 （q0，xy） F 。因此，因此，xy屬于屬于L1，x屬于屬于L1L2。得到。得到 L（M）=

21、L1L2所以，所以，L1L2是正則的。是正則的。18例例7 已知已知 L1L（a*baa*） L2L（ab*）求求L1L2。首先找到接受首先找到接受L1的的DFA如圖，如圖， Startq0q2baq1aaq3bba,b19定理定理4.9的方法構(gòu)造的方法構(gòu)造DFA M=(Q, , ，q0，F(xiàn)），），由于由于F=qi| qi Q且且 y L2，使得，使得 （qi，y） F從前圖中可以看出，從前圖中可以看出，q1，q2 F因此，接受因此，接受L1L2的自動機如下圖。這個自動機接受由正的自動機如下圖。這個自動機接受由正則表達式則表達式a*b+a*baa*表示的語言，將表示的語言，將a*b+a*baa

22、*簡化成簡化成a*ba*。因此。因此L1L2L（a*ba*）。）。 Startq0q2baaaq3bba,bq120正則代換正則代換(regular substitution) 設設、是兩個字母表，映射是兩個字母表，映射 *2:f被稱為是從被稱為是從到到的的代換代換。如果對于。如果對于 a，f(a)是是上的上的 RL RL ，則稱，則稱f f為為正則代換。正則代換。 21先將先將f的定義域擴展到的定義域擴展到*上：上： *2:*f f(f()=)= ； f(xa f(xa)=f(x)f(a)=f(x)f(a)。再將再將f的定義域擴展到的定義域擴展到*2*22:f對于對于 L *LxxfLf)(

23、)(22例例 8 設設=0，1，=a，b，f(0)=a，f(1)=b*，則則 f(010)=f(0)f(1)f(0)=ab*a f(11，00)=f(11)f(00) =f(1)f(1)f(0)f(0)=b*b*+aa=b*+aa f(L(0*(0+1)1*)=L(a*(a+b*)(b*)*) =L(a*(a+b*)b*)=L(a*ab*+a*b*b*) =L(a*b*) 23f f是正則代換是正則代換, ,則則 f()=； f()=； 對于對于 a，f(a)是是上的上的RERE； 如果如果r，s是是上的上的RERE，則，則 f(r+s)=f(r)+f(s) f(rs)=f(r)f(s) f(

24、r*)=f(r)* 是是上的上的RERE。 24定理定理 4.10 設設L是是上的一個上的一個 RL *2:f證明：證明：描述工具：描述工具：RE。對對r中運算符的個數(shù)中運算符的個數(shù)n施以歸納，證明施以歸納，證明f(r)是表示是表示f(L)的的RE。 當當n=0時時，結(jié)論成立。，結(jié)論成立。當當nk時定理成立時定理成立, ,即當即當r r中運算符的個數(shù)不大于中運算符的個數(shù)不大于k k時：時：f(L(r) = L(f(r)f(L(r) = L(f(r)。25當當n=k+1時，時， r=r1+r2。 f(L)=f(L(r) =f(L(r1+r2) =f(L(r1)L(r2)RERE的定義的定義 =f

25、(L(r1)f(L(r2)正則代換的定義正則代換的定義 =L(f(r1)L (f (r2)歸納假設歸納假設 =L(f(r1)+f (r2)RERE的定義的定義 =L(f(r1+r2)RERE的正則代換的定義的正則代換的定義 =L(f(r)26 r=r1r2。 f(L)=f(L(r) =f(L(r1r2) =f(L(r1) L(r2)RERE的定義的定義 =f(L(r1) f(L(r2)正則代換的定義正則代換的定義 =L(f(r1) L (f (r2)歸納假設歸納假設 =L(f(r1) f (r2)RERE的定義的定義 =L(f(r1r2) RERE的正則代換的定義的正則代換的定義 =L(f(r

26、)27 r=r1*。 f(L)=f(L(r) =f(L(r1*) =f(L(r1)*)RERE的定義的定義 =(f(L(r1)*正則代換的定義正則代換的定義 =(L(f(r1)*歸納假設歸納假設 =L(f(r1)*)RERE的定義的定義 =L(f(r1*)RERE的正則代換的定義的正則代換的定義 =L(f(r)28例例9 設設=0，1，2，=a=a，bb，正則代換，正則代換f f定義為：定義為： f(0)=ab； f(1)=b*a*； f(2)=a*(a+b)則：則： f(00)=abab； f(010)=abb*a*ab=ab+a+b； f(0+1+2)*)=(ab+b*a*+ a*(a+b

27、)*=(b*a*+a*(a+b)*=(a+b)*；29二、二、RL的泵引理的泵引理 泵引理泵引理(pumping lemma) 設設L為一個為一個 RL ，則存在僅依賴于，則存在僅依賴于L的正整數(shù)的正整數(shù)N，對于對于 zL，如果，如果|z|N，則存在，則存在u、v、w，滿足，滿足 z=uvw； |uv|N； |v|1； 對于任意的整數(shù)對于任意的整數(shù)i0，uviwL；30證明思想證明思想31例例 1 證明證明0n1n|n1不是不是 RL。 證明：證明： 假設假設L=0n1n|n1 是是 RL z=0N1N 按照泵引理所述按照泵引理所述 v=0kk1 此時有，此時有，u=0N-k-jw=0j1N

28、泵引理泵引理設設L為一個為一個 RL ，則存在僅，則存在僅依賴依賴于于L的正整數(shù)的正整數(shù)N，對于，對于 zL，如果，如果|z|N，則存在，則存在u、v、w，滿足，滿足 z=uvw； |uv|N； |v|1； 對于任意的整數(shù)對于任意的整數(shù)i0，uviwL；32從而有，從而有，uviw=0N-k-j(0k)i0j1N=0N+(i-1)k1N 當當i=2時，我們有：時，我們有：uv2w=0N+(2-1)k1N = 0N+k1N注意到注意到k1，所以，所以，N+kN。這就是說，這就是說，0N+k1N L這與泵引理矛盾。這與泵引理矛盾。所以，所以，L不是不是 RL。 泵引理泵引理設設L為一個為一個 RL

29、 ，則存在僅，則存在僅依賴依賴于于L的正整數(shù)的正整數(shù)N，對于，對于 zL，如果，如果|z|N，則存在，則存在u、v、w，滿足，滿足 z=uvw； |uv|N； |v|1； 對于任意的整數(shù)對于任意的整數(shù)i0，uviwL；33例例 2 證明證明0n|n為素數(shù)為素數(shù)不是不是 RL。 證明：假設證明：假設L=0n|n為素數(shù)為素數(shù) 是是 RL。 取取 z=0N+p L ，不妨設不妨設v=0k，k1 從而有，從而有，uviw=0N+p-k-j(0k)i0j=0N+p+(i-1)k泵引理泵引理設設L為一個為一個 RL ，則存在僅，則存在僅依賴依賴于于L的正整數(shù)的正整數(shù)N，對于，對于 zL，如果，如果|z|N

30、，則存在，則存在u、v、w，滿足，滿足 z=uvw； |uv|N； |v|1； 對于任意的整數(shù)對于任意的整數(shù)i0，uviwL；34當當i=N+p+1時，時，N+p+(i-1)k=N+p+(N+p+1-1)k = N+p+(N+p)k = (N+p)(1+k)注意到注意到k1，所以，所以N+p+(N+p+1-1)k=(N+p)(1+k)不是素數(shù)。故當不是素數(shù)。故當i=N+p+1時，時，uvN+p+1w=0(N+p)(1+k) L這與泵引理矛盾。這與泵引理矛盾。所以，所以，L不是不是 RL。 泵引理泵引理設設L為一個為一個 RL ，則，則存在僅依賴存在僅依賴于于L的正整的正整數(shù)數(shù)N，對于，對于 z

31、L，如，如果果|z|N，則存在，則存在u、v、w，滿足，滿足 z=uvw； |uv|N； |v|1； 對于任意的整數(shù)對于任意的整數(shù)i0，uviwL；35例例 3 證明證明0n1m2n+m|m，n1不是不是 RL。 證明：假設證明：假設L=0n1m2n+m|m，n1 是是 RL。 取取z=0N1N22N 設設 v=0k k1 從而有，從而有，uviw=0N-k-j(0k)i0j1N22N=0N+(i-1)k1N22N36uv0w=0N+(0-1)k1N22N= 0N-k1N22N 注意到注意到k1，N-k+N=2N-k|*/RL |。70如果如果(q，a)=p，f(q)= x，必有，必有f(p)

32、=xa qQ，如果，如果，f(q)=f(q0，x)=x所以，所以， a，如果，如果，p=(q，a)=(q0，x)，a)=(q0，xa)則則f(p)=f(q，a)= f(q0，x)，a)=f(q0，xa)=xa即，如果即，如果M在狀態(tài)在狀態(tài)q讀入字符讀入字符a時進入狀態(tài)時進入狀態(tài)p，則則M在在q對應的狀態(tài)對應的狀態(tài)f(q0，x)=x讀入字讀入字符符 a 時 ， 進 入時 ， 進 入 p 對 應 的 狀 態(tài)對 應 的 狀 態(tài) f ( ( q0，xa) )=xa。所以，。所以，f是是M和和M之間的同構(gòu)之間的同構(gòu)映射。映射。 71DFA的極小化的極小化 可以區(qū)分的可以區(qū)分的(distinguishab

33、le) 狀態(tài)狀態(tài)設設DFA M=(Q，q0，F(xiàn))，如果，如果 x*， 對對Q中的兩個狀態(tài)中的兩個狀態(tài)q和和p，使得，使得(q，x)F 和和(p，x)F中，有且僅有一個成立，則中，有且僅有一個成立，則稱稱p和和q是是可以可以區(qū)分區(qū)分的的。否則，稱。否則，稱q和和p等價。并記作等價。并記作qp 。72算法算法1 DFA的極小化算法的極小化算法算法思想：掃描所有的狀態(tài)對，找出所有的可區(qū)算法思想：掃描所有的狀態(tài)對，找出所有的可區(qū)分的狀態(tài)對，不可取分的狀態(tài)對一定是等價的。分的狀態(tài)對，不可取分的狀態(tài)對一定是等價的。輸入：給定的輸入：給定的DFA。輸出：可區(qū)分狀態(tài)表。輸出：可區(qū)分狀態(tài)表。主要數(shù)據(jù)結(jié)構(gòu)：狀態(tài)對

34、的關(guān)聯(lián)鏈表；可區(qū)分狀態(tài)主要數(shù)據(jù)結(jié)構(gòu)：狀態(tài)對的關(guān)聯(lián)鏈表；可區(qū)分狀態(tài)表。表。 73主要步驟主要步驟 for (q，p)F(Q-F) do標記可區(qū)分狀態(tài)表中的表項標記可區(qū)分狀態(tài)表中的表項(q，p)； for (q, ,p)FF(Q-F) (Q-F)&qp doif a，可區(qū)分狀態(tài)表中的表項，可區(qū)分狀態(tài)表中的表項(q, ,a)，(p, ,a)已被標記已被標記 thenbegin 標記可區(qū)分狀態(tài)表中的表項標記可區(qū)分狀態(tài)表中的表項(q,p)；遞歸地標記本次被標記的狀態(tài)對的遞歸地標記本次被標記的狀態(tài)對的關(guān)聯(lián)鏈表上的各個狀態(tài)對在可區(qū)分狀態(tài)表中的對關(guān)聯(lián)鏈表上的各個狀態(tài)對在可區(qū)分狀態(tài)表中的對應表項應表項e

35、nd 74else for a，doi f ( q , , a ) ( p , , a ) & ( q , , p ) 與與(q, ,a),(p, ,a)不是同一個狀態(tài)對不是同一個狀態(tài)對 then將將(q, ,p)放在放在(q, ,a),(p, ,a)的關(guān)的關(guān)聯(lián)鏈表上。聯(lián)鏈表上。 75定理定理2 對于任意對于任意DFA M=(Q，q0，F(xiàn))，Q中中的兩個狀態(tài)的兩個狀態(tài)q和和p是可區(qū)分的充要條件是是可區(qū)分的充要條件是(q，p)在在DFA的極小化算法中被標記。的極小化算法中被標記。證明：證明： 先證必要性。先證必要性。設設q和和p是可區(qū)分的，是可區(qū)分的，x是區(qū)分是區(qū)分q和和p的最短字符串。

36、的最短字符串?，F(xiàn)施歸納現(xiàn)施歸納于于x的長度，證明的長度，證明(q，p)一定被算法標記。一定被算法標記。 76當當|x|=0時時區(qū)分區(qū)分q和和p，表明，表明q和和p有且僅有一個為有且僅有一個為M的終的終止狀態(tài)，所以，止狀態(tài)，所以，(q, ,p)F(Q-F)因此，它在算法的第因此，它在算法的第(1)行被標記。行被標記。 設當設當|x|=n時結(jié)論成立時結(jié)論成立x是區(qū)分是區(qū)分q和和p的長度為的長度為n的字符串，則的字符串，則(q, ,p)被算被算法標記。法標記。 77當當|x|=n+1時時 設設x=ay，其中，其中|y|=n。由于。由于x是區(qū)分是區(qū)分q和和p的最短的最短的字符串，所以，的字符串，所以，

37、(q，x)F 和和(p，x)F中，有且僅有一個成立。不妨假設：中，有且僅有一個成立。不妨假設：(q, ,x) F ，(p, ,x)F即即(q, ,a)，y) F ，(p, ,a)，y)F設設(q, ,a)=u，(p, ,a)=v y是區(qū)分是區(qū)分u和和v的長度為的長度為n的字符串。的字符串。 78由歸納假設，由歸納假設，(u, ,v)可以被算法標記可以被算法標記。如果在考察如果在考察(q, ,p)時，時，(u, ,v)已經(jīng)被標記，則已經(jīng)被標記，則(q, ,p)在算法的第在算法的第(4)行被標記；行被標記；如果在考察如果在考察(q, ,p)時，時，(u, ,v)還沒有被標記，則還沒有被標記，則(q

38、, ,p)在算法的第在算法的第(7)行被放入到行被放入到(u, ,v)的關(guān)聯(lián)鏈的關(guān)聯(lián)鏈表中，而當表中，而當(u, ,v)被標記時，在算法的第被標記時，在算法的第(5)行行在在“遞歸遞歸”過程中過程中(q, ,p)被標記。被標記。結(jié)論對結(jié)論對|x|=n+1成立。成立。 79充分性。充分性。 設設(q, ,p)在算法中被標記。對它被標記的順序在算法中被標記。對它被標記的順序n施施歸納，證明歸納，證明q和和p是可區(qū)分的。是可區(qū)分的。 令令|F(Q-F)|=m，顯然，當，顯然，當1nm時，時，(q, ,p)是在算法的第是在算法的第(1)行被標記的，此時，行被標記的，此時，是區(qū)分是區(qū)分q和和p的字符串：

39、的字符串：(q,)F 和和(p,)F有且僅有一個成立。有且僅有一個成立。 80設設nk(km)時結(jié)論成立。即，如果時結(jié)論成立。即，如果 (q, ,p)是被算是被算法在第法在第k個或者第個或者第k個之前標記的，則存在字符串個之前標記的，則存在字符串x，x區(qū)分區(qū)分q和和p。即：。即：(q, ,x)F 和和(p, ,x)F有有且僅有一個成立。且僅有一個成立。 當當n=k+1時，如果時，如果(q, ,p)是在算法的第是在算法的第(4)行被標記的，行被標記的，此時，此時，(q, ,a)，(p, ,a)一定是在第一定是在第k個之前被個之前被標記的。設標記的。設(q, ,a)=u，(p, ,a)=v，由歸納

40、假設，由歸納假設，存在字符串存在字符串x，x區(qū)分區(qū)分u和和v：(u, ,x)F 和和(v, ,x)F有且僅有一個成立，從而，有且僅有一個成立，從而，(q, ,ax)F 和和(p, ,ax)F有且僅有一個成立。即，有且僅有一個成立。即，ax是區(qū)分是區(qū)分q和和p的字符串。的字符串。 81如果如果(q, ,p)是在算法的第是在算法的第(5)行被標記的，則它必在某行被標記的，則它必在某個狀態(tài)對個狀態(tài)對(u, ,v)的關(guān)聯(lián)鏈表中，而的關(guān)聯(lián)鏈表中，而(u, ,v)必在必在(q, ,p)之之前被標記。由歸納假設，存在前被標記。由歸納假設，存在x區(qū)分區(qū)分(u, ,v)；存在存在a，(q, ,a)=u，(p,

41、,a)=v使得使得(q, ,p)被放在被放在(u, ,v)的關(guān)聯(lián)鏈表中；的關(guān)聯(lián)鏈表中；ax是區(qū)分是區(qū)分q和和p的字符串。的字符串。所以，結(jié)論對所以，結(jié)論對n=k+1成立。由歸納法原理，結(jié)論對所成立。由歸納法原理，結(jié)論對所有有的的n成立。成立。 82定理定理3 由算法由算法1構(gòu)造的構(gòu)造的DFA在去掉不可達狀態(tài)是在去掉不可達狀態(tài)是最小最小DFA 。證明：證明：設設M=(Q,q0, ,F)為算法為算法5-1的輸入的輸入DFA，M=(Q/,q0, ,F)是相應的輸出是相應的輸出DFA。F=q|qF。對于對于 qQ/， aa，定義，定義(q，a)=(q, ,a) 83的相容性。的相容性。設設q=p ，也

42、就是說，也就是說，q和和p等價：等價：qp。即。即根據(jù)算法根據(jù)算法1，狀態(tài)，狀態(tài)q和和p是不可區(qū)分的是不可區(qū)分的(未被算未被算法標記法標記)。此時，對于此時，對于 aa，必須有，必須有(q, ,a)(p, ,a)。否則，狀態(tài)對否則，狀態(tài)對(q, ,a)，(p, ,a)必定被算法必定被算法標記，從而最終導致標記，從而最終導致(q, ,p)被算法標記。被算法標記。此與此與qp矛盾。所以，狀態(tài)矛盾。所以，狀態(tài)(q, ,a)和狀態(tài)和狀態(tài)(p, ,a) 等價：等價：(q, ,a)=(p, ,a)。所以，所以，的定義是相容的。的定義是相容的。 84L(M)=L(M) 。對對 x*，現(xiàn)施歸納于，現(xiàn)施歸納于|

43、x|，證明，證明(q0，x)=(q0，x) |x|=0 (q0,)=q0=(q0,) xx*并且并且|x|=n，(q0，xa)=(q0, ,x)，a)=(q0, ,x)，a) =(q0, ,x)，a) =(q0, ,xa) 由歸納法原理，結(jié)論對由歸納法原理，結(jié)論對 x*成立。成立。 85再由F的定義，(q0,x)=(q0,x)F (q0,x)F。所以，xL(M) xL(M)。即：L(M)=L(M)。 86證明所構(gòu)造的證明所構(gòu)造的M去掉不可達狀態(tài)后是最小去掉不可達狀態(tài)后是最小DFA。如果如果qp，則對于，則對于 xset(q)， yset(p)，x RL y不成立。不成立。事實上，如果事實上，如果qp，則存在則存在z*，z區(qū)分區(qū)分q和和p，有，有(q, ,z)=q 和和(p, ,z)= p有且僅有一個是終止狀態(tài)，這就是有且僅有一個是終止狀態(tài)，這就是說，說，xz和和yz有且僅有一個是有且僅有一個是L的句子。的句子。所以，所以，x RL y是不成立的。是不