正則表達(dá)式和有限自動(dòng)機(jī)

1、第二部分正規(guī)語言和有限自動(dòng)機(jī)語言往往是無限集，但描述的方法往往是有限的，一種方法是描述如何通過字符串操作由簡單的字符串產(chǎn)生整個(gè)語 言，或者描述如何通過集合操作由簡單語言產(chǎn)生復(fù)雜語言。另一種方法是描述識(shí)別字符串是否屬于某個(gè)語言的機(jī)制，也就 是描述一個(gè)算法過程。本書考察的最簡單的語言類是正規(guī)語言，正規(guī)語言能夠通過應(yīng)用有限次的某個(gè)標(biāo)準(zhǔn)操作從一元語言產(chǎn)生。正規(guī)語言 能夠被有限自動(dòng)機(jī)識(shí)別，有限自動(dòng)機(jī)是空間嚴(yán)格受限的簡單機(jī)器。在第二部分，我們還考察正規(guī)語言的另外一些特點(diǎn)：1）導(dǎo)出將一種語言的描述翻譯成另種語言的描述的算法；2）使用形式化方法描述語言；3）正規(guī)語言在實(shí)際中的應(yīng)用。3正則表達(dá)式和有限自動(dòng)機(jī)3.

2、1 正則語言和正則表達(dá)式注意：regular language和regular expression有時(shí)也翻譯成正規(guī)語言和正規(guī)表達(dá)式。正則語言可以從非常簡單的表達(dá)式得到，初始語言的字符串為空或單字母，僅使用合并、連接和leene連接運(yùn)算， 因此正則語言可用一個(gè)清楚的表達(dá)式描述，通常用小括號(hào)（）代替大括號(hào)，+代替稱為正則表達(dá)式。 下面是一些定義在字母表0, 1上的正則表達(dá)式，通過這些例子，能夠感受到書寫正則表達(dá)式的一些規(guī)律。語言相應(yīng)的正則表達(dá)式上a00001或000010, 1或0 - 10+10, 10或0 - 100+101, .001(1 + -j001110)*0, 1(110)*(0+

3、1)1*101*1010, 111, 11010)*(10+111 + 11010)*0, 10)*(11)* . 001, .)(0+10)* (h) *+001+ 上)我們認(rèn)為正則表達(dá)式表示的是相應(yīng)語言的最典型的字符串”，比如，1*10表示一個(gè)字符串，它以10結(jié)束，前面可以有任意多個(gè)數(shù)目的lo我們在前面將正則語言描述成：在最簡單的語言上僅僅使用三種運(yùn)算合并、連接、klee ne連接所得到的語言。這種描述預(yù)示了正則語言的遞歸定義（參見2. 4節(jié)）。下面遞歸定義不僅定義了語言，而且定義了正則表達(dá)式。定義3. 1字母表a上正則語言類r,及其相應(yīng)的正則表達(dá)式定義如下:1 .空集(即空語言)是正則語

4、言，表達(dá)式是二僅有空串的語言是正則語言，表達(dá)式是一 1。3.每個(gè)送，a是正則語言，表達(dá)式是ao如果l1和l2是正則語言，表達(dá)式是rl和r2,貝u(a) li _l2是正則語言，表達(dá)式是 rl+r2o(b) l1l2是正則語言，表達(dá)式是rlr2o(c) l1*是正則語言，表達(dá)式是rl*只有應(yīng)用上面條規(guī)則產(chǎn)生的語言才是字母表a上的正則語言。對上面的解釋做些解釋。為了保持一致性和連貫性，空語言被認(rèn)為是正則語言。后面許多地方將提到這樣的說法: 對于每個(gè)，都對應(yīng)一個(gè)正則語言。如果空語言不屬于正則語言，那么每個(gè)這樣的說法還需要排除空語言這種特殊情況，帶來不簡潔的說法。為了書寫簡潔，省去大量的括號(hào)，我們規(guī)定

5、正則表達(dá)式中運(yùn)算符的優(yōu)先級(jí)次序是dee ne*、連接、合并。同時(shí)我們借用一些代數(shù)表達(dá)式的符號(hào)，如指數(shù)幕等。原表達(dá)式簡潔表達(dá)式(rr)2 r(a+(b*)c)a+b*c(r*)r)+r同樣借助代數(shù)學(xué)的記號(hào)，兩個(gè)表示不同語言的正則表達(dá)式可以使用符號(hào)比如:(a + b)* -a + b*我們還可以借用符號(hào)二來化簡正則表達(dá)式，如正則表達(dá)式的化簡1*(1+ 上)=1* 1*1* =1*o* + 1* = 1* + 0*(0*1*)* = (0+1)*(0+1)*01(0+1)*+1*0*=(0+1)*其中一些化簡用到的規(guī)則可以從集合運(yùn)算規(guī)則得到，但另有一些是字符串運(yùn)算特有的，目前我們還沒有發(fā)現(xiàn)這種化 簡

6、的系統(tǒng)的方法(或形式化方法)，但上面的例子預(yù)示了化簡的巨大作用。比如最后一行的例子，兩個(gè)看似很復(fù)雜的語言，它們的并集卻很簡單。問題：存不存在化簡正則表達(dá)式的形式化方法(既是否存在化簡正則表達(dá)式的通用算法)？是否存在最簡潔的正則表達(dá)式？朱洪來信：我的印象中，它是 np-完全的問題。please look at garey and johnson，s book: computer and in tractibility.(由于0是偶數(shù)，因此空串上例子3.1語言l 0, 1*,由所有長度為偶數(shù)的字符串組成,屬于l ),問：l是否是正則語言？如果是，l對應(yīng)的正則表達(dá)式是什么？解答：任何一個(gè)偶數(shù)長度的字

7、符串都由多個(gè)(或0個(gè))長度為2的字符串連接而成，而字母表0, 1上的長度為2的 字符串只可能是4個(gè)：00、01、10、h,因此l可定義如下：l=00, 01, 10, 11*它的正則表達(dá)式是：(00+01 + 10+11)* 或(0+1) (0+1)*。例子3.2 l是定義在字母表0, 1上的包含奇數(shù)個(gè)1的字符串組成的語言，問l的正則表達(dá)式是什么？解答：顯然l中的字符串至少有一個(gè)1,因此一定有這樣的前綴010,其后則有偶數(shù)個(gè)(或0個(gè))1,因此可分解成多組的形式。由此得到l的正則表達(dá)式：包含奇數(shù)個(gè)1的字符串組成的語言0*)0* (10*)0*)*以最左的1為基準(zhǔn)(10*10*)*0*10*以最右

8、的1為基準(zhǔn)(10*10*)*0*10* (10*10*)*以中間的某個(gè)1為基準(zhǔn)0*1(0*10*1)*0*考慮最左1之后的后綴(0*10*1)*0*10*0* (10*10*)*1(0*10*1)*0*錯(cuò)誤的表達(dá)式有：(10*10*)*10*例子3.3 l是字母表0, 1上所有長度小于等于6的字符串組成的語言，問l的正則表達(dá)式？解答：由于l中的元 素是有限的，最簡單的方法是枚舉法：+0+1+00+01+ -+111110+111111而表示長度為n的字符串組成的語言的表達(dá)式是：n(0+1) (0+1)-(0+1) = (0+1)因此一些簡潔的表達(dá)式如下：所有長度小于等于6的字符串組成的語言上+

9、(0+1)+ (0+1) (0+1)+ +(0+1) (0+1) (0+1) (0+1) (0+1) (0+1)2 6+(0+1)+ (0+1) + +(0+1)(+0+1)6例子3. 4 l=x以1結(jié)束且不包含子串00 i x 0, 1*,問l的正則表達(dá)式？解答：字符串不包含00,則說明其中的每個(gè)0不能后接0,而且0不能是串尾字母，因此 每個(gè)0后面必定是1,既符合條件的字符串包含大量的01片斷，其間是許多1,因此初步得到的表達(dá)式是：(1+01)*但空串不符合條件，修正得到：(1+01)*(1+01) = (1+01)注意：(1+01)*1不對，漏掉了 01情況。例子3.5 c語言的標(biāo)志符的組

10、成的語言的正則表達(dá)式。解答：c語言的標(biāo)志符由3種符號(hào)組成：英文字母、數(shù)字和下劃線。而且第一個(gè)字符只能是字母或下劃線。因此： （a+b+ ,+z+a+b+ ,+z+_） （ a+b+ ,+z+a+b+ ,+z+0+1+ ,+9+_）* 我們令i是表示字母的集合，d是表示數(shù)字的集合，即： 1 = a+b+ +z+a+b+zd = 0+1+ +9則上式的簡潔表達(dá)式是：（1+_） （l+d+_）*例子3. 6 （暫空）3.2 識(shí)別語言所需要的空間語言的識(shí)別（或字符串的識(shí)別，recog nize ）問題是一個(gè)成員資格判定問題，即判定一個(gè)任意給定的字符串是否屬于某個(gè)語言。為了以后討論問題的方便，給出一些約

11、定。首先限制成從左至右的一次掃描（這簡化 了整個(gè)識(shí)別過程中應(yīng)該記住的信息總量的討論，也利于根據(jù)每步記住的信息量多少對語言分類），其次判別對象是一個(gè)特 定的字符串。除了掃描完成后，給出最后的判別（是或否），在每一步也給出假設(shè)判別，當(dāng)前的假設(shè)判別反映了已掃描的前綴的情況。最后的判別可以看成最后的、 最新的假設(shè)判別。先看看人是怎么完成識(shí)別任務(wù)，然后設(shè)計(jì)自動(dòng)機(jī)完成這項(xiàng)任務(wù)。問題是，為了給出假設(shè)判別，我們應(yīng)該記住多少前 綴信息。這里有兩種極端的情況：1 ）記住所有的前綴2）什么也不記憶。在某些情況下，我們確實(shí)可以什么也不記，如判別語言和*，前者我們忽略每步輸入，一律回答“否”；后者則一律回答“是。但多數(shù)

12、情況下，我們必須記住一些信息，應(yīng)該記住的不是字符串本身，而是字 符串表達(dá)的判別信息。稱為有限自動(dòng)機(jī)的原因是所需的空間是有限的。比如分別輸入兩個(gè)字符串x和y,得到不同的答案。這說明我們一定記住了一些不同的信息當(dāng)分別輸入x和y時(shí)， 否則我們無法區(qū)別這兩個(gè)字符串，因此通常情況下，為了識(shí)別某個(gè)語言，我們必須記住一些信息，而記住這些信息則需要 一定的空間。例子3.7語言l定義在字母表0, 1） ,由以10結(jié)尾的字符串組成。分析：顯然判定（decision） 一個(gè)字符串是否屬于語言l,只需要考察該字符串的最后兩個(gè)字符，因此在字符串輸入識(shí)別過程中，只需要記住當(dāng)前最后的兩個(gè)字符，而之前的所有字符可以忽略。字母

13、表0, 1） 的兩個(gè)字符組成的字符串只有4種，因此本例所需空間為4個(gè)單位，當(dāng)然后面會(huì)看到還可進(jìn)一步減少記住的信息，從而節(jié)省空間。例子3.8語言l定義在字母表0, 1） ,由包含偶數(shù)個(gè)0和奇數(shù)個(gè)1的字符串組成。分析：顯然，整個(gè)輸入過程中，不需要記住輸入的字符串的具體內(nèi)容，一種方法是記住當(dāng)前輸入的。和1的個(gè)數(shù)， 更簡單的方法是記住當(dāng)前輸入的。和1的個(gè)數(shù)的奇偶性，而這只有4種可能，因此本例的判定過程所需空間是4個(gè)單位。（參見圖3-1 , 77頁）例子3.9語言l=x以1結(jié)束且不包含子串00 | x. 0, 1*（參見例子3. 4）分析：假設(shè)在當(dāng)前輸入的字符串中發(fā)現(xiàn)了00子串，則我們只需要記住這個(gè)事實(shí)

14、，不管前面己經(jīng)讀過和后面將輸入的字符串是什么，能夠肯定該字符串不屬于l,不妨將這種情況記為no再考慮另兩種情況，情況0是最后一個(gè)字符是0,情況1是最后一個(gè)字符是1。出現(xiàn)情況0時(shí)，如果又看到一個(gè)0, 則轉(zhuǎn)到情況n,而情況0和情況1時(shí)看到1都轉(zhuǎn)到情況1,情況1時(shí)看到0轉(zhuǎn)到情況0o這三種情況能夠判定所有非空的字符串了，為了判定空字符串，還需要增加一個(gè)特殊的情 況。顯然所有的情況都專 注于記住最后一個(gè)字符，和是否出現(xiàn)或有可能出現(xiàn)00子串。本例需要的空間是4個(gè)單位，參見圖3-1。將例子3. 8和3. 9的討論用一個(gè)圖（圖3-1）來總結(jié)，它像一個(gè)流程圖，或展示了我們上面 判定過程的算法。圖中 每個(gè)圓表示一

15、種情況，是我們需要記住的關(guān)鍵信息，因此圓的多少表示了記住信息的多少，也表示了判定過程中需要的總 的空間的多少。每個(gè)圖中有一個(gè)起始的圓（由一個(gè)沒有源的箭頭指示），輸入的字符串從起始圓開始，沿著箭頭流動(dòng)（轉(zhuǎn)移）到下一個(gè)圓，每一次流動(dòng)消耗一個(gè)字符， 當(dāng)字符消耗完（即讀完所有字符），所停在的圓揭示了輸入字符串與圖表示的語言的關(guān)系，如果圓是雙圈，則說明該字符 串被接受，或?qū)儆谶@個(gè)語言，否則不屬于這個(gè)語言。有了這樣的圖后，任何人或機(jī)器不用理解圖中每個(gè)節(jié)點(diǎn)的具體含義，只要按照上面描述的機(jī)械的步驟動(dòng)作，就能完 成字符串的判定工作，因此刻畫了一種“抽象機(jī)”，我們不關(guān)心這種 機(jī)器的實(shí)現(xiàn)細(xì)節(jié)，比如它的驅(qū)動(dòng)動(dòng)力來自什

16、么，它表 示接受的具體信號(hào)是什么？我們關(guān)心的是它所揭示的一種形式化的過程（或算法），我們稱它為自動(dòng)機(jī)。將要證明能夠被這種自動(dòng)機(jī)識(shí)別的語言是正則語言，下面的例子顯示存在語言無法被這種自動(dòng)機(jī)識(shí)別，因此存在非 正則語言，而且我們將來的結(jié)論是非正則語言大量存在，盡管3.1節(jié)顯示的正則表達(dá)式具有靈活且強(qiáng)大的描述能力。例子3. 10語言l是例子2. 16中描述的回文語言palo分析：l的每個(gè)字符串相同于它的反寫字符串，因此從描述上看，這似乎是一種很簡單的語言，但是從判定過程所需要的空間而言，它完全不同于例子3. 7到3. 9中的語言。對于任意兩個(gè)不同的字符串x和y,都存在一個(gè)字符串z,使得xz屬于l,而y

17、z不屬于l （證明見后），因此需要區(qū)別的字符串是無窮多，自動(dòng)機(jī)需要的空間是無窮多，因此l不是有限自動(dòng)機(jī)能夠識(shí)別的語言。分三種情況討論：r1. x和y長度相同，則令z=x ；2. x比y短，設(shè)y=yiy2,其中yi與x同長，令z=wwrx，且w=y2,貝v xz是回文，而yz不是回文。3. 類似情況2。形式化的方法（即從計(jì)算機(jī)的角度）定義語言的復(fù)雜程度，而不是人腦的感覺來判定語言的復(fù)雜程度，一些人腦感 覺簡單的語言，如回文，可能是計(jì)算機(jī)認(rèn)為的復(fù)雜語言；反過來，一些計(jì)算機(jī)容易處理的語言卻可能是人腦難以把握的。 另外，計(jì)算機(jī)定義語言是從判定的角度，而不是從語言的產(chǎn)生或大小等等角度進(jìn)行的。3. 3有限

18、自動(dòng)機(jī)（finite automata ）從3. 2節(jié)的例子很容易導(dǎo)出有限自動(dòng)機(jī)的正式定義。定義3. 2：有限自動(dòng)機(jī)（finite automata, fa）是一個(gè)5元組（q, , q0, ：a）,其中 dq是一個(gè)有限集，其元素稱為狀態(tài)。是有限字母表，其元素是輸入符號(hào)。3） qo - q,是初始狀態(tài)。4） a -q,是接受狀態(tài)集。5） 一是轉(zhuǎn)移函數(shù)，從qx到q。這種定義在其他數(shù)學(xué)概念定義中很少見，數(shù)學(xué)家r. p. boas曾在發(fā)表在the americanmathematical monthly 的題為 can we make mathematics intelligible?的文中寫到：th

19、ere is a test for identifying some of the future professional mathematicians at an early age. there are stude nts who in sta ntly comprehe nd a sentence beg inning “ letx be an ordered quin tuple （a, t, 兀 a, p）, where they are evemore promisi ng if they add, n ever really un derstood it b efore.但這是計(jì)

20、算機(jī)科學(xué)，尤其是形式語言和自動(dòng)機(jī)理論中很喜愛采用的定義形式，很象是描述了一個(gè)機(jī)器的5個(gè)部件， 或程序設(shè)計(jì)語言中對象的定義。且不管它的數(shù)學(xué)含義，或是否一個(gè)5元組如何成為一個(gè)機(jī)器，它確實(shí)提供了一個(gè)有效的標(biāo)記方法。 例子3.11 （例子3. 7的進(jìn)一步討論）畫出識(shí)別語言0, 1*10的有限自動(dòng)機(jī)。見圖 3-2o我們可以簡化圖3-2所示的fao考慮狀態(tài)0和狀態(tài)00,它們都不是接受狀態(tài)，而且無論下一個(gè)字符是。還是1,都進(jìn)入同一個(gè)狀態(tài)（0進(jìn)入狀態(tài)00, 1進(jìn)入狀態(tài)01）,因此狀態(tài)0和狀態(tài)00可以合并（不妨稱為 a）, 不會(huì)改變自動(dòng)機(jī)識(shí)別的語言。同理，狀態(tài)1、狀態(tài)01和狀態(tài)11能夠合并成一個(gè)狀態(tài)（不妨稱為b

21、）,更進(jìn)一步，新狀態(tài)a可以和狀態(tài)上合并。最后簡化后的自動(dòng)機(jī)只有3個(gè)狀態(tài)，見圖3-3。 簡化后的自動(dòng)機(jī)顯然更簡潔和深刻地體現(xiàn)了語言的本質(zhì)特征，圖3-3中的狀態(tài)b含義是發(fā)現(xiàn)當(dāng)前字符為l滿足了 10結(jié)尾的一半要求，狀態(tài)10則表示滿足了全部要求。正如正則表達(dá)式可以簡化，有限自動(dòng)機(jī)也可以簡化。尋找簡化的形式化方法。刪除有限自動(dòng)機(jī)的死狀態(tài)是簡化的一 個(gè)有效方法。例子3.11的簡化方法存在形式化的方法，5. 2節(jié)會(huì)具體介紹。前面提到了自動(dòng)機(jī)的狀態(tài)轉(zhuǎn)換，定義了輸入一個(gè)字符的轉(zhuǎn)移函數(shù)，下面形式化定義輸入字符串的轉(zhuǎn)移函數(shù)，很容易 想到遞歸定義，首先需要知道字符串的遞歸定義。顯然字符串遞歸定義的起點(diǎn)是空串上，長度為

22、n的字符串由長度為n- 1的前綴和最后一個(gè)字符構(gòu)成，即x二ya。定義3.3 m=（q,送，qo,脛，函數(shù)獻(xiàn)的遞歸定義：1） q q,、* （q, 一 j二q.?） 、*（q, ya）=、c*（q, y）, a）討論，也可以認(rèn)為長度為n的字符串由第一個(gè)字符和長度為n-1的后綴構(gòu)成，即x=ay。則定義3. 3的遞歸部分也可以寫成：2）、*（q, ay）=、*（、（q, a）, y）但通常認(rèn)為定義3. 3使用更方便。根據(jù)圖3-4的自動(dòng)機(jī),計(jì)算j*(q, abc)。解答 1：、*(q, abc)=、(、*(q, ab), c)- (*(q, a), b), c) 二、(、(、*(q,上 a), b),

23、 c) 二、c(、c*(q,上)，a), b), c) 二、(q, a), b), c) 二、(、(qi, b), c) = (q2, c) 二q3 解答 2：、* (q, abc)=、*(q, abc)=*( (q, a), be) =*(qi, be) =*( (qi, b), c) =*(q 2, c) 二*(、: (q2, c),上) =*(q 3, c) =q3根據(jù)定義3. 3,有如下的結(jié)論：1. *(q, a)=、；(q, a),既是單個(gè)字符2. j*(q, xy) =*(、； *(q, x), y), x、y是字符串，可以用數(shù)學(xué)歸納法證明，參見練習(xí) 3.25有了字符串轉(zhuǎn)移函數(shù)的定

24、義，我們能夠形式化定義什么是自動(dòng)機(jī)接受的字符串和自動(dòng)機(jī)接 受的語言。定義3.4存在自動(dòng)機(jī)m=(q,送，qo, d, a),字符串x被m接受當(dāng)且僅當(dāng)6*(qo, x),否則稱為x被m拒絕，被m接受或識(shí)別的語言是，l(m)=x x被m接受。字母表7上的語言l,被自動(dòng)機(jī)m接受(accepted)或識(shí)別(recognized)的充分必要條件 是l=l(m)。注意：此處沒有區(qū)分接受(accepted)和識(shí)別(recognized)這兩種提法。有限自動(dòng)機(jī)接受的語言是由所有被m接受的字符串組成，而不是部分。有限自動(dòng)機(jī)的能力不體現(xiàn)在它的狀態(tài)數(shù)，不體現(xiàn)在它能接受的字符 串的個(gè)數(shù)，體現(xiàn)在它的鑒別能力，它接受什么樣

25、的字符串，拒絕什么樣的字符串。如果給定一個(gè)語言l,構(gòu)造接受l的自 動(dòng)機(jī)它接受所有屬于l的字符串，拒 絕所有不屬于l的字符串，而不僅僅是接受屬于l的字符串，否則圖3-5所示的自動(dòng)機(jī)接受所有的語言，失去了自動(dòng)機(jī)研究的意義。定理3.1 一個(gè)語言是正則語言當(dāng)且僅當(dāng)被一個(gè)有限自動(dòng)機(jī)接受。(kleene定理，后面證明)定理3.1揭示了，一方面，給定一個(gè)有限自動(dòng)機(jī)m,存在一個(gè)正則表達(dá)式e表示m所接受的語言，即l(m)=l(e)；另一方面，給定一個(gè)正則表達(dá)式e,存在一個(gè)有限自動(dòng)機(jī)接受e所表示的語言。第4章kleene定理的證明將給出構(gòu)造正則表達(dá)式和有限自動(dòng)機(jī)的形式化方法。這里先給出一些僅憑直覺就能 解決的簡單

26、例子，有助于導(dǎo)出最后的形式化方法。例子3. 12參見圖3-6,構(gòu)造它接受語言的正則表達(dá)式。分析：逐個(gè)分析自動(dòng)機(jī)的每個(gè)接受狀態(tài)，然后分析接受狀態(tài)的所有到達(dá)路線。本例有兩個(gè)接受狀態(tài)a和b,狀態(tài)a接受的語言是(00)*,狀態(tài)b接受的語言是(00)*11(11)*,則整個(gè)自動(dòng)機(jī)接受的語言是： (00) *+(00) *11 (11)* = (00) *(11)*例子3. 13考慮圖3. 7所示的自動(dòng)機(jī)。分析：先找到自動(dòng)機(jī)接受的最短的字符串，baaa,進(jìn)一步發(fā)現(xiàn)所有的狀態(tài)讀入b都會(huì)轉(zhuǎn)入狀態(tài)b,從起始狀態(tài)a到達(dá)接受狀態(tài)e的路徑只有一條，即abcde,因此此自動(dòng)機(jī)接受的字 符串的特征是以baaa結(jié)尾, 得到

27、正則表達(dá)式如下： (a+b)*baaa另一種思考方法是從起始狀態(tài)開始，考慮到達(dá)其他狀態(tài)所對應(yīng)的正則表達(dá)式，每一次轉(zhuǎn)移預(yù)示一個(gè)連接操作，每一次分支，預(yù)示一個(gè)合并操作，每一次循環(huán)，預(yù)示一個(gè)kleene連接操作。abcdeaabbbacbadbaeababcdeaa*bbb*acbadbaeababcdeaa*bb*a*bb*abb*acbadbaeababcdeaa*bb*a*bb*aa*bb*aabb*acbadbaeababcdeaa*bb*a*bb*aa*bb*aaa*bb*aaabb*acbadbaeababcdeaa*bb*a*bb*aa*bb*aaa*bb*aaabb*b*(ab)*a

28、b*aab*aaacbb*bb*aadbb*bb*abb*aaa+bb*aaaeabb*bb* (ab)*aabcdeaa*bb*a*bb*a(bb*a)*a*bb*aaa*bb*aaabb*b*(ab) *ab*aab*aaacbb*bb*aadbb*bb*abb*aaa+bb*aaaeabb*bb*(ab)*a往往是循環(huán)里面有循環(huán)，分支里面有分支，循環(huán)里面有分支，分支里面有循環(huán)，這樣產(chǎn)生 的表達(dá)式將會(huì)很復(fù)雜。因 此目前形式化方法得到的正則表達(dá)式并不實(shí)用，有賴進(jìn)一步發(fā)現(xiàn)簡化的方法。先給初始狀態(tài)賦初值，然后擴(kuò)展到其他狀態(tài)，然后反饋回來，反復(fù)迭代計(jì)算，直到最后穩(wěn)定下來，計(jì)算停止，一個(gè)關(guān)鍵點(diǎn)是如何

29、比較兩個(gè)正則表達(dá)式。例子3. 14反過來，給定正則表達(dá)式(11+110) *0,構(gòu)造有限自動(dòng)機(jī)接受語言l (r)o分析：空串不屬于語言l,因此初始狀態(tài)q。不是接受狀態(tài)，0屬于語言l,因此存在從初110,使得 11101后的狀態(tài)為l,引入一個(gè)狀態(tài)s,10),而且11與0和a都是始狀態(tài)到接受狀態(tài)標(biāo)記為0的轉(zhuǎn)移。另外，1和上是可區(qū)分字符串(存在字符串被拒絕，而110被接受)，因此輸入1和上，狀態(tài)q。應(yīng)該到達(dá)不同的狀態(tài)，稱輸入r,因此至少存在3個(gè)狀態(tài)，見圖3-8%如果字符串前綴為0或10,則無論后續(xù)字符串是什么，都不屬于語言 記錄字符串判定中到達(dá)失敗狀態(tài)，一旦到達(dá)s,則不再離開。繼續(xù)分析狀態(tài)r，由于字

30、符串1和11是可區(qū)分的(利用字符串可區(qū)分的，因此需要再加一個(gè)狀態(tài)t,同樣發(fā)現(xiàn)可區(qū)分字符串110,增加狀態(tài)u,這樣得到兩個(gè)接受狀態(tài)。我們發(fā)現(xiàn)沒有新的可區(qū)分狀態(tài)了，因此不用再添加狀態(tài)了，剩下的任務(wù)就是完善各個(gè)狀態(tài)的轉(zhuǎn)移函數(shù)。上面的方法稱為hit-or-miss,只要需要，就添加新狀態(tài)，直到不再添加新狀態(tài)，構(gòu)造自動(dòng)機(jī)的過程才停止。定理3.1保證了構(gòu)造正則表達(dá)式表示的語言的自動(dòng)機(jī)的過程能夠最終完成，即狀態(tài)數(shù)是有限的?，F(xiàn)在方法的最大難點(diǎn)是判斷是否需要加入新狀態(tài)，如果不需要，那么哪個(gè)已有狀態(tài)是合適的？第4章描 述的形式化方法將避開這個(gè)難點(diǎn)。3.4 區(qū)別字符串利用有限自動(dòng)機(jī)識(shí)別語言的基礎(chǔ)是自動(dòng)機(jī)不需要區(qū)分所

31、有的字符串，不需要在識(shí)別過程中記住前綴的具體內(nèi)容，正 如上節(jié)例子顯示，自動(dòng)機(jī)狀態(tài)用來區(qū)分那些需要區(qū)分的字符串。有限自動(dòng)機(jī)僅僅判別字符串是否屬于某個(gè)語言，不需要區(qū) 別不同的字符串，因此不需要記住輸入的整個(gè)字符串。有限自動(dòng)機(jī)不同狀態(tài)的數(shù)目與不同字符串的數(shù)目相關(guān)。下面我們形式化這種思想， 并揭示狀態(tài)數(shù)與區(qū)分字符串?dāng)?shù)之間的關(guān)系。定義3. 5給定字符串x和y,如果存在字符串乙使得xz和yz只有一個(gè)屬于語言l,則稱z在語言l上區(qū)分x和%如果不存在 乙則稱x和y在l上是不可區(qū)分的。根據(jù)定義3. 5,如果x和y是不可區(qū)分的，則對任意的字符串乙xz和yz到達(dá)同樣的狀態(tài)，同時(shí)被接受，或同時(shí)被拒絕。例如語言l=x

32、0, 1*x以10結(jié)尾(參見例子3. 7),字符串01011和100在l上是可區(qū)分的，因?yàn)榇嬖趜=0,區(qū)分這兩個(gè)字符串，而0和100是不可區(qū)分的。弓i理3. 1 m=(q, .1, qo, ： a)識(shí)別語言l,如果字符串x和y, * (qo, x)= *(qo, y),則x和y在l上 不可區(qū)分。證明：設(shè)z是工上的任意一個(gè)字符串，分別考察xz和yz,根據(jù)練習(xí)3. 25,、*(qo, xz)=、*(、*(q，, x), z)*(q o, yz)= *( 一*(qo, y), z)根據(jù)條件，、*(qo, xz) = *(qo, yz)可見xz和yz要么同時(shí)被m接受，要么同時(shí)被拒絕，因此x和y在m所識(shí)別的語言l上是不可區(qū)分的。l的有限自動(dòng)機(jī)的狀態(tài)數(shù)不少定理3.2假設(shè)n個(gè)字符串在語言l上兩兩可區(qū)分，那么識(shí)別于n。證明：設(shè)這n個(gè)在l上兩兩可區(qū)分的字符串是xi, x2,，x存在一個(gè)識(shí)別l、狀態(tài)數(shù)小于n的自動(dòng)機(jī)m,那么根據(jù)鴿籠法則，：*(qo, xi) /*(qo,x2)