1、2022-4-111第五章第五章 正則語言的性質(zhì)正則語言的性質(zhì)2022-4-112正則語言的描述正則語言的描述RGDFANFA-NFARERegular Language2022-4-113語言的性質(zhì)語言的性質(zhì) 語言語言的的兩種重要性質(zhì)兩種重要性質(zhì)1. 判定性質(zhì)判定性質(zhì) (Decision Properties)2. 封閉性質(zhì)封閉性質(zhì) (Closure Properties) RL性質(zhì)性質(zhì) 判定性質(zhì)：泵引理及其應用判定性質(zhì)：泵引理及其應用 封閉性質(zhì)：并、乘積、閉包、補、封閉性質(zhì)：并、乘積、閉包、補、交、正則代換、同態(tài)、逆同態(tài)的封交、正則代換、同態(tài)、逆同態(tài)的封閉性閉性 DFA的極的極小化小化 2

2、022-4-114判定性質(zhì)判定性質(zhì) Decision PropertiesDecision Properties 語言語言的判定性質(zhì)：以語言的形式化描述的判定性質(zhì)：以語言的形式化描述(例例如：如：DFA)作為輸入，判定某些性質(zhì)是否成立作為輸入，判定某些性質(zhì)是否成立的算法。的算法。 例子：例子：DFA對應的語言對應的語言L是否為空？是否為空？2022-4-115判定性質(zhì)判定性質(zhì) Decision PropertiesDecision Properties 其他判定性質(zhì)：其他判定性質(zhì)： 成員關(guān)系：成員關(guān)系：“w是否在正則語言是否在正則語言L里？里？” 空否：空否：“DFA對應語言是否為空？對應語言

3、是否為空？” 有窮否：有窮否：“DFA對應語言是否有窮？對應語言是否有窮？” “語言語言L是否為正則語言？是否為正則語言？”泵引理泵引理 兩個兩個DFA等價否：等價否：“兩個兩個DFA對應語言是否等價？對應語言是否等價？”2022-4-116判定性質(zhì)判定性質(zhì) Decision PropertiesDecision Properties 為什么要討論語言的判定性質(zhì)？為什么要討論語言的判定性質(zhì)？ 例子：當我們用例子：當我們用DFA來描述協(xié)議來描述協(xié)議(protocol)，該協(xié)議的重要性質(zhì)跟該協(xié)議的重要性質(zhì)跟DFA對應的語言相關(guān)。對應的語言相關(guān)。如：如： “該協(xié)議是否會終結(jié)？該協(xié)議是否會終結(jié)？”=“

4、該語言是否是有該語言是否是有窮的？窮的？” “該協(xié)議是否會失效？該協(xié)議是否會失效？”=“該語言是否為非該語言是否為非空的？空的？”2022-4-117判定性質(zhì)判定性質(zhì) Decision PropertiesDecision Properties 為什么要討論語言的判定性質(zhì)？為什么要討論語言的判定性質(zhì)？ 例子：我們經(jīng)常想要一個例子：我們經(jīng)常想要一個“極小的極小的”語言表語言表示，比如一個擁有最少狀態(tài)數(shù)量的示，比如一個擁有最少狀態(tài)數(shù)量的DFA或者或者一個最短的一個最短的RE 如果我們不能判定如果我們不能判定“兩個語言是否等價？兩個語言是否等價？” 或者，或者，“兩個兩個DFA是否對應相同的語言？是

5、否對應相同的語言？” 我們就無法找到我們就無法找到“極小極小”2022-4-118成員判定成員判定 Membership QuestionMembership Question 第一個判定性質(zhì)的問題：第一個判定性質(zhì)的問題：“字符串字符串w是否在是否在正則語言正則語言L里面？里面？” 假定假定L用用DFA M來描述來描述 模擬字符串模擬字符串w輸入時，輸入時，M的狀態(tài)轉(zhuǎn)移的狀態(tài)轉(zhuǎn)移Example: Testing MembershipStart10ACB100,10 1 0 1 1 NextsymbolCurrent state92022-4-11Example: Testing Members

6、hipStart10ACB100,10 1 0 1 1 NextsymbolCurrent state102022-4-11Example: Testing MembershipStart10ACB100,10 1 0 1 1 NextsymbolCurrent state112022-4-11Example: Testing MembershipStart10ACB100,10 1 0 1 1 NextsymbolCurrent state122022-4-11Example: Testing MembershipStart10ACB100,10 1 0 1 1 NextsymbolCurr

7、ent state132022-4-11Example: Testing MembershipStart10ACB100,10 1 0 1 1 NextsymbolCurrent state142022-4-112022-4-1115成員判定成員判定 Membership QuestionMembership Question 如果正則語言如果正則語言RL不是用不是用DFA來描述的怎么來描述的怎么辦？辦？RGDFANFA-NFARE定理定理 5-13 設(shè)設(shè)L是字母表是字母表上的上的 RL ，對任意，對任意x*，存在判定，存在判定x是不是是不是L的句子的算法。的句子的算法。 從一定的意義上講，接

8、受從一定的意義上講，接受L的的DFA M就是判就是判定定x是否是否L的一個句子的的一個句子的“算法算法”。 2022-4-1116成員判定成員判定 Membership QuestionMembership Question2022-4-1117空否判定空否判定 Emptiness QuestionEmptiness Question 給定一個正則語言給定一個正則語言L, 問：該語言是否包含問：該語言是否包含任何字符串？即任何字符串？即L是否為空是否為空？ 假定語言描述為假定語言描述為DFA：1. 構(gòu)建狀態(tài)轉(zhuǎn)移構(gòu)建狀態(tài)轉(zhuǎn)移圖；圖；2. 計算從開始狀態(tài)計算從開始狀態(tài)q0出發(fā)，所有可達到狀態(tài)出發(fā)，

9、所有可達到狀態(tài)的集合的集合；3. 若任何接受狀態(tài)是可到達的，則該語言非若任何接受狀態(tài)是可到達的，則該語言非空，否則該語言為空。空，否則該語言為空。2022-4-1118空否判定空否判定 Emptiness QuestionEmptiness Question 給定一個正則語言給定一個正則語言L, 問：該語言是否包含問：該語言是否包含任何字符串？即任何字符串？即L是否為空是否為空？ 判斷下列判斷下列DFA對應語言是否為空：對應語言是否為空：定理定理 5-10 設(shè)設(shè)DFA M=(Q，q0，F(xiàn))，L=L(M)非空的充分必要條件是：存在非空的充分必要條件是：存在x*，|x| 0.Since y is

10、not , we see an infinitenumber of strings in L.無窮無窮判定判定 Infiniteness QuestionInfiniteness Question2022-4-1123無窮無窮判定判定 Infiniteness Infiniteness QuestionQuestion 我們尚無一個有效算法我們尚無一個有效算法 有無窮個字符串長度大于等于有無窮個字符串長度大于等于n，我們無法，我們無法窮舉測試窮舉測試 Second idea：如果：如果L包含長度大于等于包含長度大于等于n的的字符串，那么一定包含長度介于字符串，那么一定包含長度介于n跟跟2n-1

11、的句的句子。子。2022-4-1124無窮無窮判定判定 Infiniteness Infiniteness QuestionQuestion 證明：如果證明：如果L包含長度大于等于包含長度大于等于n的字符串，的字符串，那么一定包含長度介于那么一定包含長度介于n跟跟2n-1的句子。的句子。 w=xyz，y為路徑上的第一個環(huán)為路徑上的第一個環(huán) 那么：那么：xn; 1 |y| n；zn |xz|2n 若若|xz|n，則為所求，則為所求 否則否則|xz|N。這就是說，這就是說，0N+k1N L這與泵引理矛盾。所以，這與泵引理矛盾。所以，L不是不是 RL。 2022-4-11345.1 RL的泵引理的泵

12、引理 例例 5-2 證明證明0n|n為素數(shù)為素數(shù)不是不是 RL。 證明：假設(shè)證明：假設(shè)L=0n|n為素數(shù)為素數(shù) 是是 RL。 取取 z=0N+p L ，不妨設(shè)不妨設(shè)v=0k，k1 從而有，從而有，uviw=0N+p-k-j(0k)i0j=0N+p+(i-1)k2022-4-11355.1 RL的泵引理的泵引理 當當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)(

13、1+k) L這與泵引理矛盾。所以，這與泵引理矛盾。所以，L不是不是 RL。 2022-4-11365.1 RL的泵引理的泵引理 例例 5-3 證明證明0n1m2n+m|m，n1不是不是 RL。 證明：假設(shè)證明：假設(shè)L=0n1m2n+m|m，n1 是是 RL。 取取z=0N1N22N 設(shè)設(shè)v=0k k1 從而有，從而有，uviw=0N-k-j(0k)i0j1N22N=0N+(i-1)k1N22N2022-4-11375.1 RL的泵引理的泵引理 uv0w=0N+(0-1)k1N22N= 0N-k1N22N 注意到注意到k1，N-k+N=2N-k2N0N-k1N22N L這個結(jié)論與泵引理矛盾。所以

14、，這個結(jié)論與泵引理矛盾。所以，L不是不是 RL。 2022-4-11385.1 RL的泵引理的泵引理 用來證明一個語言不是用來證明一個語言不是 RL 不能用泵引理去證明一個語言是不能用泵引理去證明一個語言是 RL。 由于泵引理給出的是由于泵引理給出的是 RL 的必要條件，所以，的必要條件，所以，在用它證明一個語言不是在用它證明一個語言不是 RL 時，我們使用反證法。時，我們使用反證法。 泵引理說的是對泵引理說的是對 RL 都成立的條件，而我們是都成立的條件，而我們是要用它證明給定語言不是要用它證明給定語言不是 RL ，這就是說，相應語，這就是說，相應語言的言的“僅僅依賴于僅僅依賴于L的正整數(shù)的

15、正整數(shù)N”實際上是不存在的。實際上是不存在的。所以，我們一定是無法給出一個具體的數(shù)的。因此，所以，我們一定是無法給出一個具體的數(shù)的。因此，人們往往就用符號人們往往就用符號N來表示這個來表示這個“假定存在假定存在”、而、而實際并不存在的數(shù)。實際并不存在的數(shù)。 2022-4-11395.1 RL的泵引理的泵引理 由于泵引理指出，如果由于泵引理指出，如果L是是 RL ，則對任，則對任意的意的zL，只要，只要|z|N，一定會存在，一定會存在u、v、w，使使uviwL對所有的對所有的i成立。因此，我們在選成立。因此，我們在選擇擇z時，就需要注意到論證時的簡潔和方便。時，就需要注意到論證時的簡潔和方便。

16、當一個特意被選來用作當一個特意被選來用作“發(fā)現(xiàn)矛盾發(fā)現(xiàn)矛盾”的的z確定以后，就必須依照確定以后，就必須依照|uv|N和和|v|1的要求，的要求，說明說明v不存在不存在(對對“存在存在u、v、w”的否定的否定) 。2022-4-11405.1 RL的泵引理的泵引理 與選與選z時類似，在尋找時類似，在尋找i時，我們也僅需要時，我們也僅需要找到一個表明矛盾的找到一個表明矛盾的“具體具體”值就可以了值就可以了(對對“所有所有i”的否定的否定)。 一般地，在證明一個語言不是一般地，在證明一個語言不是 RL 的時候，的時候，我們并不使用泵引理的第我們并不使用泵引理的第(5)條。條。 事實上，引理所要求的事

17、實上，引理所要求的|uv|N并不是必須并不是必須的。這個限制為我們簡化相應的證明提供的。這個限制為我們簡化相應的證明提供了良好支撐了良好支撐擴充了的泵引理擴充了的泵引理 。2022-4-11415.1 RL的泵引理的泵引理 2022-4-1142等價性判定等價性判定 EquivalenceEquivalence 問：給定問：給定RL語言語言L與與M，是否，是否L=M？ 從從L跟跟M的的DFA出發(fā)，構(gòu)建一個出發(fā)，構(gòu)建一個乘積乘積DFA (product DFA) 讓讓L跟跟M的的DFA擁有狀態(tài)集擁有狀態(tài)集Q和和R 乘積乘積DFA有狀態(tài)集為有狀態(tài)集為Q R 即，對于即，對于q Q, r R, q,r是乘積是乘積DFA的一個的一個狀態(tài)狀態(tài)2022-4-1143等價性判定等價性判定 EquivalenceEquivalence 乘積乘積DFA：開始狀態(tài)：開始狀態(tài)：q0,r0轉(zhuǎn)移函數(shù)：轉(zhuǎn)移函數(shù)：(q,r, a) = L(q,a), M(r,a) 因此，我們用乘積因此，我們用乘積DFA的狀態(tài)同時去模擬的狀態(tài)同時去模擬兩個兩個DFA的移