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

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

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

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

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

6、ormal Form定義定義2.5 2.5 稱一個上下文無關文法稱一個上下文無關文法 G = (V, G = (V,R,S) ,R,S) 為喬為喬姆斯基范式，假設它的每一個規那么具有如下方式姆斯基范式，假設它的每一個規那么具有如下方式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 任一上下文無關文法任一上下文無關文法 G = (V, G = (V,R,S) ,R,S) 為言語為

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

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

9、sj ,棧字母表棧字母表 - 形狀形狀 qk Q 形狀集合形狀集合PDA M: - 調轉到一個新的形狀調轉到一個新的形狀, - 推入元素推入元素 (非確定性地非確定性地)PDA的根本構造 下推自動機下推自動機M被定義為被定義為6元組元組 (Q， ， ，q0，F)，這里，這里Q， ， 和和F都是有窮集合，并且：都是有窮集合，并且： Q 是形狀集是形狀集 是輸入字母表是輸入字母表 棧字符表棧字符表 q0 Q是起始形狀是起始形狀 F Q是接受形狀集是接受形狀集 是形狀轉移函數是形狀轉移函數 相當于相當于3種語句種語句goto, push ,pop : Q P (Q )= = 2.2.1 PDA 的方

10、式化定義的方式化定義PDA 的計算過程的計算過程一臺下推自動機一臺下推自動機M接受輸入接受輸入w，假設可以把，假設可以把w寫成寫成w=w1w2wm，這里每一個，這里每一個wi ，并且存在形狀，并且存在形狀序列序列r0, r1, , rm Q和字符串序列和字符串序列s0, s1, , sm T*滿足下述滿足下述3個條件，字符串個條件，字符串si是是M在計算的接受分支中的在計算的接受分支中的棧內容序列。棧內容序列。r0 q0 且且s0，對于對于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 背景：背景： 檢查左右括號檢查左右括號(0,1)能否能否 配對配對 PDA 首先把首先把 “ $ 0n 推入棧推入棧. $ 棧底符號，壓箱錢棧底符號，壓箱錢 ，表示后來壓入棧的，表示后來壓入棧的存款用完了。存款用完了。然后，當讀到然后，當讀到“1n, 0被彈出被彈出. 棧頂對比，左右括號配對，那么同歸于盡，棧頂對比，左右括號配對，那么同歸于盡，最后最后, 假設假設“$留在棧頂，那么接受留在棧頂，那么接受q1q3q2q4, $, $1, 01, 00, 02.2.2 PDA 舉例舉例q1讀讀，棧頂，棧頂變箱底錢變箱底錢 q2遇左括號遇左括號0，壓，壓0棧入棧入棧

12、棧q1q3q2q4, $, $1, 01, 00, 0彈出壓箱錢，棧空彈出壓箱錢，棧空 q3 遇右括號遇右括號1，彈出，彈出0，10兌消兌消在在q2遇遇1，彈，彈出出0, 兌消兌消形狀圖描畫形狀圖描畫方式化定義方式化定義接受接受 w = 000111 形狀；堆棧的變化過程：形狀；堆棧的變化過程：(q1; ) (q2; $) (q2; 0$) (q2; 00$) (q2; 000$) (q3; 00$) (q3; 0$) (q3; $) (q4; ) 終態終態 q4 是個接受態是個接受態形狀形狀棧內值棧內值 q1q3q2q4, $, $1, 01, 00, 0w = 000111回絕回絕 w =

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

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

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

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

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

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