計(jì)算理論第2章去某范式版ppt課件

1、第一部分 自動(dòng)機(jī)與言語第2章 上下文無關(guān)文法上下文無關(guān)文法的引入v對(duì)任何言語對(duì)任何言語L L，有一個(gè)字母表，有一個(gè)字母表，使得，使得L L* * 。 vL L的詳細(xì)組成構(gòu)造是什么樣的？的詳細(xì)組成構(gòu)造是什么樣的？v一個(gè)給定的字符串能否為一個(gè)給定言語的句子一個(gè)給定的字符串能否為一個(gè)給定言語的句子? ?假設(shè)假設(shè)不是，它在構(gòu)造的什么地方出了錯(cuò)？進(jìn)一步地，這個(gè)錯(cuò)不是，它在構(gòu)造的什么地方出了錯(cuò)？進(jìn)一步地，這個(gè)錯(cuò)誤是什么樣的錯(cuò)？如何更正？誤是什么樣的錯(cuò)？如何更正？。v這些問題對(duì)有窮言語來說，比較容易處理。這些問題對(duì)有窮言語來說，比較容易處理。v這些問題對(duì)無窮言語來說，不太容易處理。這些問題對(duì)無窮言語來說，不

2、太容易處理。v用文法作為相應(yīng)言語的有窮描畫不僅可以描畫出言語用文法作為相應(yīng)言語的有窮描畫不僅可以描畫出言語的構(gòu)造特征，而且還可以產(chǎn)生這個(gè)言語的一切句子的構(gòu)造特征，而且還可以產(chǎn)生這個(gè)言語的一切句子文法文法(grammar) (grammar) 文法的方式定義 文法的方式定義 文法例 1CDccd#，CDd#，CD#d，S)。商定商定 推導(dǎo)(derivation)定義定義文法的構(gòu)造例1 文法的構(gòu)造例2文法的構(gòu)造例 3不能用不能用Aan表示表示A可以產(chǎn)生恣意多個(gè)可以產(chǎn)生恣意多個(gè)a。文法的喬姆斯基體系 文法的喬姆斯基體系 文法的喬姆斯基體系 文法的喬姆斯基體系 文法的喬姆斯基體系 文法的喬姆斯基體系

3、定理 2.1 上下文無關(guān)文法概述 上下文無關(guān)文法例如 上下文無關(guān)文法例如 2.1.1 上下文無關(guān)文法的方式化定義上下文無關(guān)文法的方式化定義定義定義2.1 2.1 上下文無關(guān)文法是一個(gè)上下文無關(guān)文法是一個(gè)4 4元組元組 G=(V, G=(V,R,S),R,S) V: V: 一個(gè)有窮集，稱為變元集一個(gè)有窮集，稱為變元集 : : 一個(gè)有窮集一個(gè)有窮集 (V (V= =) ) ，稱為終結(jié)符集，稱為終結(jié)符集 R: R: 有窮規(guī)那么集，有窮規(guī)那么集， V V (V (V) )* * 規(guī)那么是規(guī)那么是 左一右多，或一分為多左一右多，或一分為多 S SV : V : 起始變元起始變元文法文法 G G的言語可以

4、表示為的言語可以表示為 L(G): L(G):L(G) = wL(G) = w* * | S | S * * w w 上下文無關(guān)文法舉例上下文無關(guān)文法舉例2.1.2 上下文無關(guān)文法舉例上下文無關(guān)文法舉例2.1.3 設(shè)計(jì)上下文無關(guān)文法設(shè)計(jì)上下文無關(guān)文法2.1.3 設(shè)計(jì)上下文無關(guān)文法設(shè)計(jì)上下文無關(guān)文法2.1.4 岐義性岐義性假設(shè)文法以不同的方式產(chǎn)生同一個(gè)字符串，那么稱文法假設(shè)文法以不同的方式產(chǎn)生同一個(gè)字符串，那么稱文法歧義地產(chǎn)生這個(gè)字符串，假設(shè)一個(gè)文法歧義地產(chǎn)生某個(gè)歧義地產(chǎn)生這個(gè)字符串，假設(shè)一個(gè)文法歧義地產(chǎn)生某個(gè)字符串，那么稱這個(gè)文法是歧義的字符串，那么稱這個(gè)文法是歧義的2.1.4 岐義性岐義性定

5、義定義2.4 假設(shè)字符串假設(shè)字符串w在上下文無關(guān)文法在上下文無關(guān)文法G中有兩個(gè)以中有兩個(gè)以上不同的最左派生，那么稱上不同的最左派生，那么稱G歧義地產(chǎn)生字符串歧義地產(chǎn)生字符串w，假，假設(shè)文法設(shè)文法G歧義地產(chǎn)生某個(gè)字符串，那么稱歧義地產(chǎn)生某個(gè)字符串，那么稱G是歧義的；是歧義的；留意：有時(shí)對(duì)于一個(gè)歧義文法，可以找到一個(gè)產(chǎn)生一留意：有時(shí)對(duì)于一個(gè)歧義文法，可以找到一個(gè)產(chǎn)生一樣言語的非歧義文法，但是，某些上下文無關(guān)言語只樣言語的非歧義文法，但是，某些上下文無關(guān)言語只能用歧義文法產(chǎn)生，這樣的言語稱為固有歧義的。能用歧義文法產(chǎn)生，這樣的言語稱為固有歧義的。2.1.5 喬姆斯基范式喬姆斯基范式Chomsky N

6、ormal Form定義定義2.5 2.5 稱一個(gè)上下文無關(guān)文法稱一個(gè)上下文無關(guān)文法 G = (V, G = (V,R,S) ,R,S) 為喬為喬姆斯基范式，假設(shè)它的每一個(gè)規(guī)那么具有如下方式姆斯基范式，假設(shè)它的每一個(gè)規(guī)那么具有如下方式A A BC BC 一分為二一分為二或或A A a a 或終極化或終極化其中，其中， A AV and B,CV and B,CV S, and aV S, and a 2.1.5 喬姆斯基范式喬姆斯基范式Chomsky Normal Form定理定理2.6 2.6 任一上下文無關(guān)文法任一上下文無關(guān)文法 G = (V, G = (V,R,S) ,R,S) 為言語為

7、言語都可以用一個(gè)喬姆斯基范式的上下文無關(guān)文法產(chǎn)生都可以用一個(gè)喬姆斯基范式的上下文無關(guān)文法產(chǎn)生證明思緒：證明思緒：1添加一個(gè)新的起始變元添加一個(gè)新的起始變元S0； 和規(guī)那么和規(guī)那么S0S 2思索一切的諸如思索一切的諸如A 規(guī)那么；規(guī)那么；R uAv, 添加添加R uv；R uAvAw, 添加添加R uvAw; R uAvw; R uvwR A, 添加添加R 3處置一切的單一規(guī)那么；處置一切的單一規(guī)那么； 4添加新的變元和規(guī)那么，把留下的一切規(guī)那添加新的變元和規(guī)那么，把留下的一切規(guī)那么轉(zhuǎn)換成適宜的變元；么轉(zhuǎn)換成適宜的變元； 例例例習(xí)題2.2 下推自動(dòng)機(jī)Pushdown Automata有窮自動(dòng)機(jī)的

8、物理模型PDA的物理模型的物理模型例例輸入 w = 00100100111100101internal state set Qxyyzxstack當(dāng)讀完W且進(jìn)入終止態(tài)，那么接受w, 棧用來作簡單記憶歷史對(duì)比，只是棧頂元素可見，才干有限，且不靈敏例例非方式化地描畫關(guān)于言語非方式化地描畫關(guān)于言語0n1n | n=0的的PDA如何如何任務(wù)的：任務(wù)的：PDA 的方式化描畫的方式化描畫輸入 w = 00100100111100101內(nèi)部形狀集合內(nèi)部形狀集合State set Qxyyzx棧棧PDA M 讀帶讀帶 w且且 作棧操作取決于作棧操作取決于 - 輸入輸入 wi ,輸入字輸入字母表母表 - 棧棧

9、sj ,棧字母表?xiàng)Ｗ帜副?- 形狀形狀 qk Q 形狀集合形狀集合PDA M: - 調(diào)轉(zhuǎn)到一個(gè)新的形狀調(diào)轉(zhuǎn)到一個(gè)新的形狀, - 推入元素推入元素 (非確定性地非確定性地)PDA的根本構(gòu)造 下推自動(dòng)機(jī)下推自動(dòng)機(jī)M被定義為被定義為6元組元組 (Q， ， ，q0，F(xiàn))，這里，這里Q， ， 和和F都是有窮集合，并且：都是有窮集合，并且： Q 是形狀集是形狀集 是輸入字母表是輸入字母表 棧字符表?xiàng)Ｗ址?q0 Q是起始形狀是起始形狀 F Q是接受形狀集是接受形狀集 是形狀轉(zhuǎn)移函數(shù)是形狀轉(zhuǎn)移函數(shù) 相當(dāng)于相當(dāng)于3種語句種語句goto, push ,pop : Q P (Q )= = 2.2.1 PDA 的方

10、式化定義的方式化定義PDA 的計(jì)算過程的計(jì)算過程一臺(tái)下推自動(dòng)機(jī)一臺(tái)下推自動(dòng)機(jī)M接受輸入接受輸入w，假設(shè)可以把，假設(shè)可以把w寫成寫成w=w1w2wm，這里每一個(gè)，這里每一個(gè)wi ，并且存在形狀，并且存在形狀序列序列r0, r1, , rm Q和字符串序列和字符串序列s0, s1, , sm T*滿足下述滿足下述3個(gè)條件，字符串個(gè)條件，字符串si是是M在計(jì)算的接受分支中的在計(jì)算的接受分支中的棧內(nèi)容序列。棧內(nèi)容序列。r0 q0 且且s0，對(duì)于對(duì)于i=0, , m-1，有，有ri+1 ，b (ri， wi+1 ，a)其中其中si=at, si+1=bt, a, b T 和和t T*；rm F例例2.9

11、 : L = 0n1n | n0 背景：背景： 檢查左右括號(hào)檢查左右括號(hào)(0,1)能否能否 配對(duì)配對(duì) PDA 首先把首先把 “ $ 0n 推入棧推入棧. $ 棧底符號(hào)，壓箱錢棧底符號(hào)，壓箱錢 ，表示后來壓入棧的，表示后來壓入棧的存款用完了。存款用完了。然后，當(dāng)讀到然后，當(dāng)讀到“1n, 0被彈出被彈出. 棧頂對(duì)比，左右括號(hào)配對(duì)，那么同歸于盡，棧頂對(duì)比，左右括號(hào)配對(duì)，那么同歸于盡，最后最后, 假設(shè)假設(shè)“$留在棧頂，那么接受留在棧頂，那么接受q1q3q2q4, $, $1, 01, 00, 02.2.2 PDA 舉例舉例q1讀讀，棧頂，棧頂變箱底錢變箱底錢 q2遇左括號(hào)遇左括號(hào)0，壓，壓0棧入棧入棧

12、棧q1q3q2q4, $, $1, 01, 00, 0彈出壓箱錢，?？諒棾鰤合溴X，棧空 q3 遇右括號(hào)遇右括號(hào)1，彈出，彈出0，10兌消兌消在在q2遇遇1，彈，彈出出0, 兌消兌消形狀圖描畫形狀圖描畫方式化定義方式化定義接受接受 w = 000111 形狀；堆棧的變化過程：形狀；堆棧的變化過程：(q1; ) (q2; $) (q2; 0$) (q2; 00$) (q2; 000$) (q3; 00$) (q3; 0$) (q3; $) (q4; ) 終態(tài)終態(tài) q4 是個(gè)接受態(tài)是個(gè)接受態(tài)形狀形狀棧內(nèi)值棧內(nèi)值 q1q3q2q4, $, $1, 01, 00, 0w = 000111回絕回絕 w =

13、 0101 形狀；堆棧的變化過程：形狀；堆棧的變化過程：(q1; ) (q2; $) (q2; 0$) (q3; $) (q4; ) 雖然具有輸入的部分子串雖然具有輸入的部分子串 “01，但找不到整個(gè)字，但找不到整個(gè)字符串的接受途徑符串的接受途徑了解為用括號(hào)配對(duì)比較直觀了解為用括號(hào)配對(duì)比較直觀形狀形狀棧內(nèi)值棧內(nèi)值 q1q3q2q4, $, $1, 01, 00, 0w = 0101例：例：構(gòu)造一臺(tái)識(shí)別下述言語的構(gòu)造一臺(tái)識(shí)別下述言語的PDA M：aibjck i, j, k0 且且 i=j 或或 i=k例確定的(deterministic)PDA2.2.3與上下文無關(guān)文法的等價(jià)性與上下文無關(guān)文法

14、的等價(jià)性定理定理.12: 一個(gè)言語是上下文無關(guān)的，當(dāng)且一個(gè)言語是上下文無關(guān)的，當(dāng)且僅當(dāng)存在一臺(tái)僅當(dāng)存在一臺(tái)PDA識(shí)別它。識(shí)別它。L是是CFL L被被PDA接受接受兩步兩步: 1)引理引理. 假設(shè)一個(gè)言語是上下文無關(guān)的，那么假設(shè)一個(gè)言語是上下文無關(guān)的，那么存在一臺(tái)存在一臺(tái)PDA識(shí)別它識(shí)別它 部分部分2)引理引理.5 假設(shè)一個(gè)言語被一臺(tái)假設(shè)一個(gè)言語被一臺(tái)PDA識(shí)別，那么識(shí)別，那么它是上下文無關(guān)的它是上下文無關(guān)的 部分部分假設(shè)干教材都說假設(shè)干教材都說 此定理容易證明此定理容易證明 但又略去證明，此但又略去證明，此定理的證明定理的證明適宜靜心自學(xué)，不適宜課堂講解適宜靜心自學(xué)，不適宜課堂講解 。 可以先

15、成認(rèn)結(jié)論，可以先成認(rèn)結(jié)論，讀第二遍時(shí)再深化了解讀第二遍時(shí)再深化了解引理2.13 的證明P的非方式描畫如下：的非方式描畫如下：1) 把標(biāo)志符把標(biāo)志符$和起始變元放入棧中；和起始變元放入棧中；2反復(fù)下述步驟：反復(fù)下述步驟：假設(shè)棧頂是變元假設(shè)棧頂是變元A，那么非確定地選擇一個(gè)關(guān)，那么非確定地選擇一個(gè)關(guān)于于A的規(guī)那么，并且把的規(guī)那么，并且把A交換成這條規(guī)那么右交換成這條規(guī)那么右邊的字符串；邊的字符串；假設(shè)棧項(xiàng)是終結(jié)符假設(shè)棧項(xiàng)是終結(jié)符a，那么讀輸入中的下一個(gè)，那么讀輸入中的下一個(gè)符號(hào)，并且把它與符號(hào)，并且把它與a進(jìn)展比較。假設(shè)它們匹配，進(jìn)展比較。假設(shè)它們匹配，那么反復(fù)，假設(shè)它們不匹配，那么這個(gè)非確定那么

16、反復(fù)，假設(shè)它們不匹配，那么這個(gè)非確定性分支回絕；性分支回絕；假設(shè)棧頂是符號(hào)假設(shè)棧頂是符號(hào)$，那么進(jìn)入接受形狀，假設(shè)，那么進(jìn)入接受形狀，假設(shè)此刻輸入已全部讀完，那么接受這個(gè)輸入。此刻輸入已全部讀完，那么接受這個(gè)輸入。1初始化棧，把符號(hào)初始化棧，把符號(hào)$和和S推入棧；推入棧；2 a)棧頂是個(gè)變元；令棧頂是個(gè)變元；令(qloop, , A)(qloop, w) A w是是R中的一條規(guī)那么中的一條規(guī)那么 b)棧頂是個(gè)終結(jié)符。令棧頂是個(gè)終結(jié)符。令(qloop, a, a) (qloop, ) c)棧頂是空棧標(biāo)志符棧頂是空棧標(biāo)志符$。令。令(qloop, , $)(qaccept, ) CFG G 轉(zhuǎn)換成

17、轉(zhuǎn)換成PDA P例：把下述例：把下述CFG G轉(zhuǎn)換成一臺(tái)轉(zhuǎn)換成一臺(tái)PDA： SaTb b TTa 引理2.15的證明自學(xué)引理2.15 的證明引理2.1 證明3正那么言語與上下文無關(guān)言語的關(guān)正那么言語與上下文無關(guān)言語的關(guān)系系Regularlanguagescontext-free languages? 0n1n 2.3 非上下文無關(guān)言語非上下文無關(guān)言語言語言語 L = anbncn | n0 不是不是CFL證明此事需求新的泵定理言多必反復(fù)證明此事需求新的泵定理言多必反復(fù)比喻：前后文無關(guān)的人格，我行我素，不受言論左比喻：前后文無關(guān)的人格，我行我素，不受言論左右，兩岸猿聲啼不住，輕舟已過萬重山，那么

18、某些右，兩岸猿聲啼不住，輕舟已過萬重山，那么某些喜好和行為就會(huì)反復(fù)喜好和行為就會(huì)反復(fù)如：如： A * vAy :If S * uAz * uvAyz * uvxyz L, then S * uAz * uvAyz * * uviAyiz * uvixyiz L as well, for all i=0,1,2, 關(guān)于上下文無關(guān)言語的泵引理的思想：關(guān)于上下文無關(guān)言語的泵引理的思想： 與與RL不同，不同，CFL 兩處打圈，至少一處是兩處打圈，至少一處是真圈，真圈，定理定理2.19：假設(shè)：假設(shè)A是上下文無關(guān)言語，那么存在數(shù)是上下文無關(guān)言語，那么存在數(shù)p泵泵長度，使得長度，使得A中任何一個(gè)長度不小于中任何一個(gè)長度不小于p的字符串的字符串s被劃被劃分成分成5段段 s=uvxyz 且滿足下述條件：且滿足下述條件：1) 對(duì)于每一個(gè)對(duì)于每一個(gè)I=0，uvixy