自動(dòng)機(jī)與形式語言_第五章_泵引理

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ì)：泵引理及其應(yīng)用判定性質(zhì)：泵引理及其應(yīng)用 封閉性質(zhì)：并、乘積、閉包、補(bǔ)、封閉性質(zhì)：并、乘積、閉包、補(bǔ)、交、正則代換、同態(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對(duì)應(yīng)的語言對(duì)應(yīng)的語言L是否為空？是否為空？2022-4-115判定性質(zhì)判定性質(zhì) Decision PropertiesDecision Properties 其他判定性質(zhì)：其他判定性質(zhì)： 成員關(guān)系：成員關(guān)系：“w是否在正則語言是否在正則語言L里？里？” 空否：空否：“DFA對(duì)應(yīng)語言是否為空？對(duì)應(yīng)語言

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

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

5、否對(duì)應(yīng)相同的語言？” 我們就無法找到我們就無法找到“極小極小”2022-4-118成員判定成員判定 Membership QuestionMembership Question 第一個(gè)判定性質(zhì)的問題：第一個(gè)判定性質(zhì)的問題：“字符串字符串w是否在是否在正則語言正則語言L里面？里面？” 假定假定L用用DFA M來描述來描述 模擬字符串模擬字符串w輸入時(shí)，輸入時(shí)，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 ，對(duì)任意，對(duì)任意x*，存在判定，存在判定x是不是是不是L的句子的算法。的句子的算法。 從一定的意義上講，接

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

9、所有可達(dá)到狀態(tài)的集合的集合；3. 若任何接受狀態(tài)是可到達(dá)的，則該語言非若任何接受狀態(tài)是可到達(dá)的，則該語言非空，否則該語言為空。空，否則該語言為空。2022-4-1118空否判定空否判定 Emptiness QuestionEmptiness Question 給定一個(gè)正則語言給定一個(gè)正則語言L, 問：該語言是否包含問：該語言是否包含任何字符串？即任何字符串？即L是否為空是否為空？ 判斷下列判斷下列DFA對(duì)應(yīng)語言是否為空：對(duì)應(yīng)語言是否為空：定理定理 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 我們尚無一個(gè)有效算法我們尚無一個(gè)有效算法 有無窮個(gè)字符串長(zhǎng)度大于等于有無窮個(gè)字符串長(zhǎng)度大于等于n，我們無法，我們無法窮舉測(cè)試窮舉測(cè)試 Second idea：如果：如果L包含長(zhǎng)度大于等于包含長(zhǎng)度大于等于n的的字符串，那么一定包含長(zhǎng)度介于字符串，那么一定包含長(zhǎng)度介于n跟跟2n-1

11、的句的句子。子。2022-4-1124無窮無窮判定判定 Infiniteness Infiniteness QuestionQuestion 證明：如果證明：如果L包含長(zhǎng)度大于等于包含長(zhǎng)度大于等于n的字符串，的字符串，那么一定包含長(zhǎng)度介于那么一定包含長(zhǎng)度介于n跟跟2n-1的句子。的句子。 w=xyz，y為路徑上的第一個(gè)環(huán)為路徑上的第一個(gè)環(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為素?cái)?shù)為素?cái)?shù)不是不是 RL。 證明：假設(shè)證明：假設(shè)L=0n|n為素?cái)?shù)為素?cái)?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的泵引理的泵引理 當(dāng)當(dāng)i=N+p+1時(shí)，時(shí)，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)不是素?cái)?shù)。故當(dāng)不是素?cái)?shù)。故當(dāng)i=N+p+1時(shí)，時(shí)，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這個(gè)結(jié)論與泵引理矛盾。所以

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

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

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

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