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

1、第一部分 自動(dòng)機(jī)與語言,第1章 正則語言 研究內(nèi)容 有窮自動(dòng)機(jī) 非確定性 正則表達(dá)式 非正則語言,第2章 上下文無關(guān)文法,研究內(nèi)容 上下文無關(guān)文法概述 下推自動(dòng)機(jī) 非上下文無關(guān)語言,上下文無關(guān)文法的引入,有窮自動(dòng)機(jī)和正則表達(dá)式這兩種不同但等價(jià)的描述語言的方法，雖然能描述許多語言，但還有一些簡單的語言不能用它們描述，如：0n1n | n=0 于是，需引入一種能力更強(qiáng)的描述語言數(shù)學(xué)模型上下文無關(guān)文法，它能夠描述某些應(yīng)用廣泛的具有遞歸結(jié)構(gòu)特征的語言,對任何語言L，有一個(gè)字母表，使得L* 。 L的具體組成結(jié)構(gòu)是什么樣的？ 一個(gè)給定的字符串是否為一個(gè)給定語言的句子?如果不是，它在結(jié)構(gòu)的什么地方出了錯(cuò)？進(jìn)

2、一步地，這個(gè)錯(cuò)誤是什么樣的錯(cuò)？如何更正？。 這些問題對有窮語言來說，比較容易解決。 這些問題對無窮語言來說，不太容易解決。 用文法作為相應(yīng)語言的有窮描述不僅可以描述出語言的結(jié)構(gòu)特征，而且還可以產(chǎn)生這個(gè)語言的所有句子,文法(grammar,例：1）哈爾濱是美麗的城市 2）北京是祖國的首都 3）集合是數(shù)學(xué)的基礎(chǔ) 4）形式語言是很抽象的 4個(gè)句子的主體結(jié)構(gòu) =哈爾濱，北京，集合，形式語言 =是美麗的城市，是祖國的首都，是數(shù)學(xué)的基礎(chǔ)，是很抽象的,可以是 或者 。 =北京、哈爾濱、形式語言、集合、美麗的城市、祖國的首都、數(shù)學(xué)的基礎(chǔ)。 =是。 =很抽象的。 把取名為,表示成形式 是,表示一個(gè)語言，需要4種

3、東西 形如的 “符號” 它們表示相應(yīng)語言結(jié)構(gòu)中某個(gè)位置上可以出現(xiàn)的一些內(nèi)容。每個(gè)“符號”對應(yīng)的是一個(gè)集合，在該語言的一個(gè)具體句子中，句子的這個(gè)位置上能且僅能出現(xiàn)相應(yīng)集合中的某個(gè)元素。所以，這種“符號”代表的是一個(gè)語法范疇。 所有的“規(guī)則”，都是為了說明的結(jié)構(gòu)而存在，相當(dāng)于說，定義的就是,形如北京的“符號” 它們是所定義語言的合法句子中將出現(xiàn)的“符號”。僅僅表示自身，稱為終極符號。 所有的“規(guī)則”都呈的形式 在產(chǎn)生語言的句子中被使用，稱這些“規(guī)則”為產(chǎn)生式,文法的形式定義,G=(V, , R, S) V為變量(variable)的非空有窮集。AV，A叫做一個(gè)語法變量(syntactic Vari

4、able)，簡稱為變量，也可叫做非終極符號(nonterminal)。它表示一個(gè)語法范疇(syntactic Category)。 為終極符(terminal)的非空有窮集。a ，a叫做終極符。由于中變量表示語法范疇， 中的字符是語言的句子中出現(xiàn)的字符，所以，有V =。 SSV，為文法G的開始符號(start symbol,文法的形式定義,R為產(chǎn)生式(production)的非空有窮集合。R中的元素均具有形式，被稱為產(chǎn)生式，讀作：定義為。其中(V)+，且中至少有V中元素的一個(gè)出現(xiàn)。(V)*。稱為產(chǎn)生式的左部，稱為產(chǎn)生式的右部。產(chǎn)生式又叫做定義式或者語法規(guī)則,文法例 1,例 ： 以下四元組都是文

5、法。 (A，0，1，A01，A0A1，A1A0，A)。 (A，0，1，A0，A0A，A)。 (A，B，0，1，A01，A0A1，A1A0，BAB，B0，A)。 (A，B，0，1，A0，A1，A0A，A1A ，A)。 (S，A，B，C，D, a，b，c，d,#，SABCD，Sabc#，AaaA，ABaabbB，BCbbccC，cCcccC，CDccd#，CDd#，CD#d，S,約定,對一組有相同左部的產(chǎn)生式 1，2 ， ，n 可以簡單地記為： 1|2|n 讀作：定義為1，或者2，或者n。并且稱它們?yōu)楫a(chǎn)生式。1，2，n稱為候選式(candidate,使用符號 英文字母表較為前面的大寫字母，如A，B

6、，C，表示語法變量； 英文字母表較為前面的小寫字母，如a，b，c，表示終極符號； 希臘字母，表示由語法變量和終極符號組成的行,推導(dǎo)(derivation,設(shè)G= (V, , R, S)是一個(gè)文法，如果R，(V )*，則稱在G中直接推導(dǎo)出。 G 讀作：在文法G中直接推導(dǎo)出。 “直接推導(dǎo)”可以簡稱為推導(dǎo)(derivation)，也稱推導(dǎo)為派生,定義,語言(language) L(G)=w | w *且S * w 句子(sentence) wL(G)，w稱為G產(chǎn)生的一個(gè)句子。 句型(sentential form) G=(V， ，R，S)，對于(V)*，如果S * ，則稱是G產(chǎn)生的一個(gè)句型,定義,句

7、子w是從S開始，在G中可以推導(dǎo)出來的終極符號行，它不含語法變量。 句型是從S開始，在G中可以推導(dǎo)出來的符號行，它可能含有語法變量。 等價(jià)(equivalence) 設(shè)有兩個(gè)文法G1和G2，如果L(G1)= L(G2)，則稱G1與G2等價(jià),文法的構(gòu)造例1,例：構(gòu)造文法G，使L(G)=0，1，00，11 G1：S0|1|00|11 G2：SA|B|AA|BB，A0，B1 G3：S0|1|0A|1B，A0，B1 G4：SA|B|AA|BB，A0，B1 G5：SA|B|BB，A0，B1，CACS21，C11，C2,文法的構(gòu)造例2,L=0n|n1 G6：S0|0S L=0n|n0 G7：S|0S L=0

8、2n13n|n0 G8：S|00S111,文法的構(gòu)造例 3,例：構(gòu)造文法G9，使L(G9)=w|wa，b，z+。 G9：SA|AS Aa|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z 用SA|AS生成 An。 不可以用Aa|b|c|z表示。Aa|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z 不可以用Aa8表示Aaaaaaaaa。 不能用Aan表示A可以產(chǎn)生任意多個(gè)a,文法的喬姆斯基體系,文法G=(V， ，R，S) G叫做0型文法(type 0 grammar)，也叫做短語結(jié)構(gòu)文法(phr

9、ase structure grammar, PSG)。 L(G)叫做0型語言。也可以叫做短語結(jié)構(gòu)語言(PSL)、遞歸可枚舉集(recursively enumerable ，r.e.,文法的喬姆斯基體系,G是0型文法。 如果對于R，均有|成立，則稱G為1型文法(type 1 grammar)，或上下文有關(guān)文法(context sensitive grammar,CSG)。 L(G)叫做1型語言(type 1 language)或者上下文有關(guān)語言(context sensitive language ,CSL,文法的喬姆斯基體系,G是1型文法 如果對于R，均有|，并且V成立，則稱G為2型文法(

10、type 2 grammar)，或上下文無關(guān)文法(context free grammar,CFG)。 L(G)叫做2型語言(type 2 language)或者上下文無關(guān)語言(context free language ,CFL,文法的喬姆斯基體系,G是2型文法 如果對于R，均具有形式 Aw AwB 其中A，BV，w +。則稱G為3型文法(type 3 grammar)，也可稱為正則文法(regular grammar ,RG)或者正規(guī)文法。 L(G)叫做3型語言(type 3 language)，也可稱為正則語言或者正規(guī)語言(regular language ,RL,文法的喬姆斯基體系,如

11、果一個(gè)文法G是RG（3型文法），則它也是CFG（2型文法）、CSG（1型文法）和短語結(jié)構(gòu)文法（0型文法）。反之不一定成立。 如果一個(gè)文法G是CFG，則它也是CSG和短語結(jié)構(gòu)文法。反之不一定成立。 如果一個(gè)文法G是CSG，則它也是短語結(jié)構(gòu)文法。反之不一定成立。 相應(yīng)地： RL也是CFL、CSL和短語結(jié)構(gòu)語言。反之不一定成立,文法的喬姆斯基體系,CFL也是CSL和短語結(jié)構(gòu)語言。反之不一定成立。 CSL也是短語結(jié)構(gòu)語言。反之不一定成立 當(dāng)文法G是CFG時(shí)，L(G)卻可以是RL。 當(dāng)文法G是CSG時(shí)，L(G)可以是RL、CSL。 當(dāng)文法G是短語結(jié)構(gòu)文法時(shí)，L(G)可以是RL、CSL和CSL,定理,定理

12、 ： L是RL（正則語言）的充要條件是存在一個(gè)文法，該文法產(chǎn)生語言L，并且它的產(chǎn)生式要么是形如：Aa的產(chǎn)生式，要么是形如AaB的產(chǎn)生式。其中A、B為語法變量，a為終極符號,2.1 上下文無關(guān)文法概述,文法G=(V， ，R，S)被稱為是上下文無關(guān)文法或2型文法。 如果對于R，均有|，并且V成立。 關(guān)鍵：對于AV，如果AP，則無論A出現(xiàn)在句型的任何位置，我們都可以將A替換成，而不考慮A的上下文。 L(G)叫做2型語言(type 2 language)或者上下文無關(guān)語言(context free language ,CFL,上下文無關(guān)文法示例,上下文無關(guān)文法示例,2.1.1 上下文無關(guān)文法的形式化定

13、義,定義2.1 上下文無關(guān)文法是一個(gè)4元組 G=(V,R,S) V: 一個(gè)有窮集，稱為變元集 : 一個(gè)有窮集 (V=) ，稱為終結(jié)符集 R: 有窮規(guī)則集， V (V)* 規(guī)則是 左一右多，或一分為多 SV : 起始變元 文法 G的語言可以表示為 L(G): L(G) = w* | S * w,上下文無關(guān)文法舉例,2.1.2 上下文無關(guān)文法舉例,2.1.3 設(shè)計(jì)上下文無關(guān)文法,2.1.3 設(shè)計(jì)上下文無關(guān)文法,利用正則 考察子串 利用遞歸,2.1.4 岐義性,如果文法以不同的方式產(chǎn)生同一個(gè)字符串，則稱文法歧義地產(chǎn)生這個(gè)字符串，如果一個(gè)文法歧義地產(chǎn)生某個(gè)字符串，則稱這個(gè)文法是歧義的,2.1.4 岐義

14、性,定義2.4 如果字符串w在上下文無關(guān)文法G中有兩個(gè)以上不同的最左派生，則稱G歧義地產(chǎn)生字符串w，如果文法G歧義地產(chǎn)生某個(gè)字符串，則稱G是歧義的； 注意：有時(shí)對于一個(gè)歧義文法，能夠找到一個(gè)產(chǎn)生相同語言的非歧義文法，但是，某些上下文無關(guān)語言只能用歧義文法產(chǎn)生，這樣的語言稱為固有歧義的,2.1.5 喬姆斯基范式Chomsky Normal Form,定義2.5 稱一個(gè)上下文無關(guān)文法 G = (V,R,S) 為喬姆斯基范式，如果它的每一個(gè)規(guī)則具有如下形式 A BC 一分為二 或A a 或終極化 其中， AV and B,CV S, and a,2.1.5 喬姆斯基范式Chomsky Normal

15、Form,定理2.6 任一上下文無關(guān)文法 G = (V,R,S) 為語言都可以用一個(gè)喬姆斯基范式的上下文無關(guān)文法產(chǎn)生,證明思路：1）添加一個(gè)新的起始變元S0； 和規(guī)則S0S 2）考慮所有的諸如A 規(guī)則； R uAv, 添加R uv； R uAvAw, 添加R uvAw; R uAvw; R uvw R A, 添加R 3）處理所有的單一規(guī)則； 4）添加新的變元和規(guī)則，把留下的所有規(guī)則轉(zhuǎn)換成合適的變元,例,例,試將下列文法轉(zhuǎn)換成等價(jià)的 CNF。 SbA | aB AbAA | aS | a BaBB | bS | b,先引入變量Ba，Bb和產(chǎn)生式Baa，Bbb ，完成第一步變換。 SBbA | B

16、aB ABbAA | BaS | a BBaBB | BbS | b Baa Bbb,引入新變量B1、B2 SBbA | BaB ABbB1 | BaS | a BBaB2 | BbS | b Baa Bbb B1AA B2BB,不能因?yàn)樵瓉碛挟a(chǎn)生式A a和B b而放棄引進(jìn)變量Ba 、Bb和產(chǎn)生式Baa 、Bbb。 L(A)=x | xa，b+ & x中a的個(gè)數(shù)比b的個(gè)數(shù)恰多1個(gè)。 L(B)=x | xa，b+ & x中b的個(gè)數(shù)比a的個(gè)數(shù)恰多1個(gè)。 L(Ba)= a 。 L(Bb)= b,習(xí)題,試將下列文法轉(zhuǎn)換成等價(jià)的 CNF。 SaBB | bAA BaBa | aa | AbbA ,2.2

17、 下推自動(dòng)機(jī)Pushdown Automata,下推自動(dòng)機(jī)PDA：描述CFL（上下文無關(guān)語言）的設(shè)備 PDA： “硬件” 增加了棧（先進(jìn)后出），使其能識別某些非正則語言 PDA： 與上下文無關(guān)文法等價(jià),有窮自動(dòng)機(jī)的物理模型,PDA的物理模型,FSC：表示狀態(tài)和轉(zhuǎn)移函數(shù) 棧：“先進(jìn)后出”的存儲設(shè)備，能保存無限的信息量 推入：向棧寫一個(gè)符號 彈出：從棧中刪除一個(gè)符號,例,例,非形式化地描述關(guān)于語言0n1n | n=0的PDA如何工作的,PDA 的形式化描述,輸入 w = 00100100111100101,內(nèi)部狀態(tài)集合 State set Q,PDA M 讀帶 w 且 作棧操作取決于 - 輸入 w

18、i ,輸入字母表 - 棧 sj ,棧字母表 - 狀態(tài) qk Q 狀態(tài)集合PDA M: - 調(diào)轉(zhuǎn)到一個(gè)新的狀態(tài), - 推入元素 (非確定性地,PDA的基本結(jié)構(gòu),PDA應(yīng)該含有三個(gè)基本結(jié)構(gòu) 存放輸入符號串的輸入帶。 存放文法符號的棧。 有窮狀態(tài)控制器。 PDA的動(dòng)作 在有窮狀態(tài)控制器的控制下根據(jù)它的當(dāng)前狀態(tài)、棧頂符號、以及輸入符號作出相應(yīng)的動(dòng)作，在有的時(shí)候，不需要考慮輸入符號,下推自動(dòng)機(jī)M被定義為6元組 (Q，q0，F(xiàn))，這里Q，和F都是有窮集合，并且： Q 是狀態(tài)集 是輸入字母表 棧字符表 q0 Q是起始狀態(tài) F Q是接受狀態(tài)集 是狀態(tài)轉(zhuǎn)移函數(shù) 相當(dāng)于3種語句goto, push ,pop :

19、Q P (Q ) = =,2.2.1 PDA 的形式化定義,q，a，Z)=(p1，1)，(p2，2)，(pm，m) 表示M在狀態(tài)q，棧頂符號為Z時(shí)，讀入字符a，對于i=1，2，m，可以選擇地將狀態(tài)變成pi，并將棧頂符號Z彈出，將i中的符號從右到左依次壓入棧，然后將讀頭向右移動(dòng)一個(gè)帶方格而指向輸入字符串的下一個(gè)字符,q，Z)=(p1，1)，(p2，2)，(pm，m) 表示M進(jìn)行一次-移動(dòng)(空移動(dòng))，即M在狀態(tài)q，棧頂符號為Z時(shí)，無論輸入符號是什么，對于i=1，2，m，可以選擇地將狀態(tài)變成pi，并將棧頂符號Z彈出，將i中的符號從右到左依次壓入棧，讀頭不移動(dòng),PDA 的計(jì)算過程,一臺下推自動(dòng)機(jī)M接受

20、輸入w，如果能夠把w寫成w=w1w2wm，這里每一個(gè)wi ，并且存在狀態(tài)序列r0, r1, , rm Q和字符串序列s0, s1, , sm T*滿足下述3個(gè)條件，字符串si是M在計(jì)算的接受分支中的棧內(nèi)容序列。 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 : L = 0n1n | n0 背景： 檢查左右括號(0,1)是否 配對 PDA 首先把 “ $ 0n ” 推入棧. $ 棧底符號，壓箱錢 ，表示后來壓入棧的存款用完了。 然后，當(dāng)讀到“1n”, 0被彈出.

21、棧頂對比，左右括號配對，則同歸于盡， 最后, 如果“$”留在棧頂，則接受,2.2.2 PDA 舉例,狀態(tài)圖描述,用“a, b c”表示當(dāng)機(jī)器從輸入中讀a時(shí)可用c替換棧頂?shù)姆朾。 若a是，則機(jī)器作這個(gè)轉(zhuǎn)移，而不讀取輸入中的任何符號。 若b是，則機(jī)器作這個(gè)轉(zhuǎn)移，而不讀棧中的任何符號，也不從棧中彈出任何符號。若c是，則不在棧中寫任何符號,形式化定義,w = 000111,w = 0101,例：構(gòu)造一臺識別下述語言的PDA M：aibjck i, j, k0 且 i=j 或 i=k,例,例 ： 構(gòu)造接受L=wwT|w0,1*的PDA,確定的(deterministic)PDA,PDA在每一個(gè)狀態(tài)q和

22、一個(gè)棧頂符號下的動(dòng)作都是惟一的。 關(guān)鍵 對于(q，Z)Q，M此時(shí)如果有非空移動(dòng)，就不能有空移動(dòng)。 每一種情況下的移動(dòng)都是惟一的。 非確定的PDA和確定型PDA識別能力不同，非確定型PDA能識別確定型PDA不能識別的語言,2.2.3與上下文無關(guān)文法的等價(jià)性,定理.12: 一個(gè)語言是上下文無關(guān)的，當(dāng)且僅當(dāng)存在一臺PDA識別它。 L是CFL L被PDA接受,兩步: 1)引理. 如果一個(gè)語言是上下文無關(guān)的，則存在一臺PDA識別它 部分 2)引理.5 如果一個(gè)語言被一臺PDA識別，則它是上下文無關(guān)的 部分 若干教材都說 此定理容易證明 但又略去證明，此定理的證明 適合靜心自學(xué)，不適合課堂講解 。 可以先

23、承認(rèn)結(jié)論， 讀第二遍時(shí)再深入理解,引理2.13 的證明（,引理2.13 如果一個(gè)語言是上下文無關(guān)的，則存在一臺下推自動(dòng)機(jī)識別它。 證明思路 設(shè)A 是CFL，根據(jù)定義，存在一個(gè)CFG G產(chǎn)生它。說明如何把G轉(zhuǎn)換成一臺等價(jià)的PDA P。 確定是否存在關(guān)于輸入w的派生PDA P當(dāng)G產(chǎn)生w時(shí)，接受這個(gè)輸入。 派生是當(dāng)文法產(chǎn)生一個(gè)字符串時(shí)的替換序列，派生的每一步產(chǎn)生一個(gè)變元和終結(jié)符的中間字符串。 設(shè)計(jì)P，以確定是否有一系列使用G的規(guī)則替換，能夠從起始變元導(dǎo)出w 檢驗(yàn)是否有關(guān)于w的派生。 困難在于判斷要替換， PDA的非確定性使得它能夠猜想出正確的替換序列， 在派生的每一步，非確定地選擇關(guān)于某個(gè)變元的一條

24、規(guī)則，并且對這個(gè)變元做替換,P的非形式描述如下： 1) 把標(biāo)記符$和起始變元放入棧中； 2）重復(fù)下述步驟： 如果棧頂是變元A，則非確定地選擇一個(gè)關(guān)于A的規(guī)則，并且把A替換成這條規(guī)則右邊的字符串； 如果棧項(xiàng)是終結(jié)符a，則讀輸入中的下一個(gè)符號，并且把它與a進(jìn)行比較。如果它們匹配，則重復(fù)，如果它們不匹配，則這個(gè)非確定性分支拒絕； 如果棧頂是符號$，則進(jìn)入接受狀態(tài)，如果此刻輸入已全部讀完，則接受這個(gè)輸入,1）初始化棧，把符號$和S推入棧； 2） a)棧頂是個(gè)變元；令(qloop, , A)(qloop, w) A w是R中的一條規(guī)則 b)棧頂是個(gè)終結(jié)符。令(qloop, a, a) (qloop, )

25、 c)棧頂是空棧標(biāo)記符$。令(qloop, , $)(qaccept, ),CFG G 轉(zhuǎn)換成PDA P例：把下述CFG G轉(zhuǎn)換成一臺PDA： SaTb b TTa,引理2.15的證明（）自學(xué),引理2.15 如果一個(gè)語言被一臺下推自動(dòng)機(jī)識別，則它是上下文無關(guān)的。 證明思路 現(xiàn)有一臺PDA P，要構(gòu)造一個(gè)CFG G，它產(chǎn)生P接受的所有字符串。換言之，如果一個(gè)字符串能使P從它的起始狀態(tài)轉(zhuǎn)移到一個(gè)接受狀態(tài)，則G應(yīng)該產(chǎn)生這個(gè)字符串。 為了獲得這個(gè)結(jié)果，我們設(shè)計(jì)一個(gè)能做更多事情的文法。對于P的每一對狀態(tài)p和q，文法有一個(gè)變元Apq。它產(chǎn)生所有能夠把P從p和空棧一塊帶到q和空棧的字符串?？梢钥闯霾还軛５膬?nèi)

26、容是什么，這樣的字符串也能夠把P從p帶到q，并且保持棧的內(nèi)容在狀態(tài)q和在狀態(tài)p時(shí)樣,引理2.15 的證明（,為簡化工作，對P作修改，使其具有以下三個(gè)特點(diǎn)。 1）有唯一的接受狀態(tài)qaccept 。 2）在接受之前清空棧。 3）每一個(gè)轉(zhuǎn)移把一個(gè)符號推入棧(推入動(dòng)作)，或者把一個(gè)符號彈出棧(彈出動(dòng)作)，但不同時(shí)做這兩個(gè)動(dòng)作。 使P具有特點(diǎn)1和2較容易，使P具有特點(diǎn)3就要把每一個(gè)同時(shí)彈出和推入的轉(zhuǎn)移替換成兩個(gè)轉(zhuǎn)移，中間要經(jīng)過一個(gè)新的狀態(tài)；把每一個(gè)既不彈出也不推入的轉(zhuǎn)移替換成兩個(gè)轉(zhuǎn)移，先推入任意一個(gè)棧符號，然后再把它彈出,引理2.1 證明（3,設(shè)計(jì)G，使得Apq產(chǎn)生把P從p帶到q并且以空棧開始和結(jié)束的所有字符串，了解P對這樣的字符串如何運(yùn)行。 對于任一的字符串x，P的每個(gè)動(dòng)作是推入或是彈出，但對空棧不能彈出，對x的第一個(gè)動(dòng)作一定是推入。因結(jié)束時(shí)?？?，對x的最后一個(gè)動(dòng)作一定是彈出。 在P對x的計(jì)算過程 兩情況：僅在開始和結(jié)束時(shí)，棧是空的；或者除開始和結(jié)束時(shí)之外，在計(jì)算中的某個(gè)地方，棧變成空的。如是前情況，最后彈出的符號一定就是開始時(shí)推入的那個(gè)符號。用規(guī)則ApqaArsb模擬前一種情況，其中a是在做第一個(gè)動(dòng)作時(shí)讀的輸入符號，b是在做最后一個(gè)動(dòng)作時(shí)讀的輸入符號，r是跟在p后面的狀態(tài)，s是q的前一個(gè)狀態(tài)。用規(guī)則ApqAp