自然語言理解講義第二章課件

1、自然語言理解講義第二章 句法與句法分析(1): 形式語言與自動(dòng)機(jī)第1頁，共39頁。內(nèi)容提要如何描述語言形式文法定義喬姆斯基的文法層級(jí)索引文法范疇文法自動(dòng)機(jī)文法判定的復(fù)雜度用形式文法描述自然語言文法、語言與自動(dòng)機(jī)的關(guān)系第2頁，共39頁。如何描述一種語言枚舉 給出語言中的所有句子 對(duì)于含無限多個(gè)句子的語言不合適文法(語法) 給出生成語言中所有句子的方法 當(dāng)且僅當(dāng)能夠用該方法產(chǎn)生的句子才屬于該語言自動(dòng)機(jī) 給出識(shí)別該語言中句子的機(jī)械方法第3頁，共39頁。形式文法(1)形式文法：四元組G = 終結(jié)符（Terminals）的有限集合VT 終結(jié)符是句子中實(shí)際出現(xiàn)的符號(hào) 相當(dāng)于單詞表（有時(shí)也稱為字母表）非終結(jié)

2、符（Non-terminals）的有限集合VN 非終結(jié)符在句子中不實(shí)際出現(xiàn) 但在推導(dǎo)中起變量作用 相當(dāng)于語言中的語法范疇第4頁，共39頁。形式文法(2)起始符S S屬于VN 相當(dāng)于句法范疇中的句子重寫式規(guī)則(Rewriting Rules)的有限集合P或 產(chǎn)生式規(guī)則(Production Rules)的有限集合P 基本形式： 含義：將改寫成 和是終結(jié)符和非終結(jié)符組成的串 非空，可以為空() 第5頁，共39頁。形式文法(3)定義 V*=(VNVT)*，V*。V*是VN和VT上的任意字符串，包括空串()。 V+ =V*-。 直接推導(dǎo)： x y 如果xy是P中的一條規(guī)則推導(dǎo)： * 如果可以經(jīng)過多次直

3、接推導(dǎo)得到語言：L(G)= | VT*；S * 第6頁，共39頁。一個(gè)例子例：設(shè)形式文法G的VT=the, John, ate, apple，VN=S, NP, VP, ART, N, V, NAME, P=1. SNP VP, 2. VPV NP, 3. NPNAME, 4. NPART N, 5. NAMEJohn, 6. Vate, 7. ARTthe, 8. Ncat，其中NP代表名詞短語、VP代表動(dòng)詞短語等等。則句子“John ate the apple”的生成過程如下 SNP VP (重寫S) NAME VP (重寫NP) John VP (重寫NAME) John V NP (重

4、寫VP) John ate NP (重寫V) John ate ART N (重寫NP) John ate the N (重寫ART) John ate the apple (重寫N) 第7頁，共39頁。喬姆斯基的文法層級(jí)0型文法1型文法2型文法3型文法第8頁，共39頁。喬姆斯基0型文法短語結(jié)構(gòu)文法，無限制重寫文法 PSG：Phrasal Structure Grammar對(duì)規(guī)則形式的約束對(duì)于規(guī)則形式?jīng)]有任何限制第9頁，共39頁。喬姆斯基1型文法上下文有關(guān)語法，上下文敏感語法CSG：Context Sensitive Grammar對(duì)規(guī)則形式的約束： ，是任意串，且的長(zhǎng)度小于的長(zhǎng)度 A A是非

5、終結(jié)符， 、是任意串 以上兩種形式等價(jià) 敏感：在一定的上下文環(huán)境下A可改寫為第10頁，共39頁。喬姆斯基2型文法上下文無關(guān)文法，上下文自由文法 CFG：Context Free Grammar對(duì)規(guī)則形式的約束： A ：A是非終結(jié)符，是任意串 在任何上下文環(huán)境下A可改寫為第11頁，共39頁。上下文無關(guān)文法的一個(gè)例子SaASSaASbAAbaSaASaAaaSbAaaabAaaabbaa第12頁，共39頁。喬姆斯基3型文法正規(guī)文法，正則文法 RG：Regular Grammar對(duì)規(guī)則形式的約束 ABx或者Ax，A,B是非終結(jié)符，x是終結(jié)符一部正則文法可以表示為一個(gè)正則表達(dá)式 例子：ab|c*+d|

6、ef|g|h+第13頁，共39頁。喬姆斯基層級(jí)以外的文法類別介于CFG和CSG之間的語法類別 索引文法（IG: Index Grammar） 可以生成anbncn形式的語言 樹粘接文法 TAG：Tree Adjoining Grammar與喬姆斯基語法層級(jí)相交叉的語法類別第14頁，共39頁。索引文法(1)索引文法是一個(gè)五元組（VN, VT,VI,P,S)VN,VT,S與前面的定義相同VI是索引的有限集合P是重寫規(guī)則的有限集合，規(guī)則形式為：1) A2) AB(f)3) A(f)A , B VN, f VI, (VNVT)*第15頁，共39頁。索引文法(2)直接推導(dǎo)()的定義如果AX1X2Xk是規(guī)

7、則集中具有1)形式的規(guī)則，那么：A()X1(1) X2(2)Xk(k)其中，XiVN時(shí)，i；XiVT時(shí)，i如果AB(f)是規(guī)則集中具有2)形式的規(guī)則，那么A()B(f) 如果A(f)X1X2Xk是規(guī)則集中具有3)形式的規(guī)則，那么：A(f)X1(1) X2(2)Xk(k)其中，XiVN時(shí)，i；XiVT時(shí)，i推導(dǎo)(*)的定義和語言的定義與前面類似第16頁，共39頁。索引文法(3) 例子（規(guī)則集）S S()S ABCA() aAB() bBC() cCA aB bC c 推導(dǎo)SS() S() S() A()B()C() aA()B()C() aaA()B()C() aaaaB()C() aaaabb

8、bbcccc可以生成anbncn形式的語言，不是CFG第17頁，共39頁。其他文法鏈文法（Link Grammar）依存文法（Dependency Grammar）范疇文法（CategorialGrammar）第18頁，共39頁。范疇文法(1)Montague,1970。鄒崇理,1995。蔣嚴(yán)&潘海華,1998。白碩,1998范疇文法的核心思想是把語言中的各種成分對(duì)應(yīng)為某種“類型”/“范疇”，把語言結(jié)構(gòu)的構(gòu)造過程對(duì)應(yīng)為“類型”/“范疇”之間的演算過程。http:/www.cs.man.ac.uk/ai/CG/第19頁，共39頁。范疇文法(2)：基本概念范疇文法里面有兩種基本范疇：S和N。粗略地

9、理解，S相當(dāng)于句子，N相當(dāng)于名詞。一個(gè)語言成分的范疇（類型）由基本范疇S,N加上范疇表達(dá)式構(gòu)造符“”，“/”，括號(hào)“（”，和“）”構(gòu)成。范疇構(gòu)造符“”表示“左缺”；“/”表示“右缺”，直觀上，可以把它們?cè)O(shè)想為除號(hào)，相應(yīng)地，范疇的構(gòu)造就可以看成是帶有方向的除法運(yùn)算。括號(hào)表示結(jié)合順序。當(dāng)兩個(gè)語言成分之間發(fā)生結(jié)合關(guān)系時(shí)，它們相應(yīng)的范疇則發(fā)生對(duì)應(yīng)的“乘法”運(yùn)算。運(yùn)算中最關(guān)鍵的操作就是“約分”。第20頁，共39頁。范疇文法(3)：英語詞類的范疇表示詞類 范疇標(biāo)注 說明句子 S 基本范疇名詞 N 基本范疇不及物動(dòng)詞 NS 左方缺少主語及物動(dòng)詞 (NS)/N或者N(S/N) 左方少主語，右方少賓語形容詞(做

10、定語) N/N 右方少中心語形容詞(做表語) (S/N)S 左方少“缺賓語句子”副詞(做前置狀語) (NS)/(NS) 右方少中心語副詞(做后置狀語) (NS)(NS) 左方少中心語介詞(做后置狀語) (NS)(NS)/N 右方少介詞賓語介詞(做后置定語) (NN)/N 右方少介詞賓語冠詞 N/N 右方少名詞代詞(主格) S/(NS) 右方少不及物動(dòng)詞代詞(賓格) (S/N)S 左方少“缺賓語句子”第21頁，共39頁。范疇文法(4)：范疇演算句子的構(gòu)造過程就是語言成分所對(duì)應(yīng)的范疇的演算過程。一個(gè)單詞串的演算的結(jié)果或者是S，或者不是S，前者即為合法的句子，后者則是不合法的句子。演算的具體操作分為

11、兩種：一種叫做“應(yīng)用”(Application)，簡(jiǎn)記為A；一種叫做“合成”(Composition)，簡(jiǎn)記為C。應(yīng)用就是完整的約分，即分母被約掉，只剩下分子作為結(jié)果；比如： S/N N S N NS S 合成就是約分后范疇表達(dá)式仍然帶著分母。比如： S/(NS) (NS)/N S/N第22頁，共39頁。范疇文法(5)：范疇詞典he S/(NS)is (NS)/Na N/Nclever N/Nboy N第23頁，共39頁。范疇文法(6)：范疇詞典He is a clever boy.S/(NS) (NS)/N N/N N/N N-CS/N -C S/N -C S/N -A S第24頁，共39頁

12、。范疇演算的語言學(xué)假設(shè)假設(shè)了所有結(jié)構(gòu)都是由詞匯負(fù)載的，這樣才能從詞匯的范疇標(biāo)記推導(dǎo)出各個(gè)上級(jí)結(jié)構(gòu)成分的范疇標(biāo)記；假設(shè)了所有結(jié)合必定是鄰接成分的結(jié)合，而不可能有跨越鄰接成分的超距結(jié)合，這樣才能依托鄰接關(guān)系實(shí)現(xiàn)范疇標(biāo)記的約分計(jì)算；假設(shè)了嚴(yán)格的語序關(guān)系，這樣才能從確定方向上找到約分的對(duì)象；假設(shè)了每個(gè)結(jié)構(gòu)必須填項(xiàng)完備，這樣才能在最后獲得一個(gè)分母約干凈了的S標(biāo)記。第25頁，共39頁。范疇文法存在的問題1 范疇標(biāo)記和詞類不是一一對(duì)應(yīng)的，要在具體的語流中確定具體詞的范疇標(biāo)記有相當(dāng)?shù)碾y度，甚至無異于先要理解。2 不負(fù)載在詞上面的結(jié)構(gòu)（如漢語中的聯(lián)合結(jié)構(gòu)、連謂結(jié)構(gòu)等）就很難納入范疇語法的框架中去表達(dá)。3 超距相

13、關(guān)的成分（如“王冕死了父親”中的“王冕”和“父親”）在范疇文法的框架中無法建立約分關(guān)系。4 象漢語這樣語序靈活、填項(xiàng)經(jīng)常不完備（省略）的語言，用范疇文法去描述會(huì)遇到許多麻煩問題。第26頁，共39頁。圖靈機(jī)(1)：直觀描述B B B B a1 a2 ai an B B B B B B有限狀態(tài)控制器雙向可讀寫紙帶在每一個(gè)時(shí)刻，可以定義圖靈機(jī)的格局為(q,a,i)其中q為當(dāng)前狀態(tài)，a為當(dāng)前紙帶上的字符串，i為當(dāng)前讀寫頭的位置。B為空白字符。第27頁，共39頁。圖靈機(jī)(2)：形式定義圖靈機(jī)是一個(gè)六元組 M= ( Q, , , , q0, F) Q為自動(dòng)機(jī)狀態(tài)的有限集合 一個(gè)有限的字符集合，其中空白字符

14、B , 為輸入字符集合，B 是一個(gè)狀態(tài)轉(zhuǎn)移函數(shù)：QQR,L,S R,L,S分布表示讀寫頭左移、右移或者不動(dòng) q0Q為初始狀態(tài) FQ為終止?fàn)顟B(tài)集第28頁，共39頁。圖靈機(jī)(3)：能接受的字符串開始時(shí)，紙帶中間有n個(gè)字符構(gòu)成輸入串，余下的無窮多個(gè)字符為空白字符，空白字符不是輸入符號(hào)開始時(shí)，讀寫頭處于輸入串的最左端，圖靈機(jī)的狀態(tài)為q0如果圖靈機(jī)M對(duì)于字符串在執(zhí)行過程中進(jìn)入某個(gè)接受狀態(tài)，稱為M接受字符串；如果執(zhí)行過程中遇到一個(gè)格局在狀態(tài)轉(zhuǎn)移函數(shù)中沒有定義，那么稱M不接受字符串第29頁，共39頁。線性有界自動(dòng)機(jī)線性有界自動(dòng)機(jī)的構(gòu)造與圖靈機(jī)完全一致對(duì)圖靈機(jī)的限制：紙帶存在一個(gè)左右邊界（用兩個(gè)特殊符號(hào)來標(biāo)識(shí)

15、），圖靈機(jī)的執(zhí)行過程中讀寫頭位置不能超出邊界線性有界自動(dòng)機(jī)所識(shí)別的語言等價(jià)于1型語法所生成的語言第30頁，共39頁。下推自動(dòng)機(jī)下推自動(dòng)機(jī)是一個(gè)七元組M=( Q, , , , q0, Z0, F ) Q為自動(dòng)機(jī)狀態(tài)的有限集合 為輸入紙帶上字符的有限集合 為堆棧字符的有限集合 q0Q為初始狀態(tài) Z0是堆棧中的一個(gè)特殊符號(hào)，表示棧底 FQ為終止?fàn)顟B(tài)集是一個(gè)狀態(tài)轉(zhuǎn)移函數(shù)：Q()Q*第31頁，共39頁。有限狀態(tài)自動(dòng)機(jī)有限狀態(tài)自動(dòng)機(jī)是一個(gè)七元組M=( Q, I, U, , , q0, F ) Q為自動(dòng)機(jī)狀態(tài)的有限集合I為輸入字符的有限集合O為輸出字符的有限集合是一個(gè)狀態(tài)轉(zhuǎn)移函數(shù)：QIQ是一個(gè)輸出函數(shù)：QI

16、Uq0Q為初始狀態(tài)FQ為終止?fàn)顟B(tài)集第32頁，共39頁。兩種有限狀態(tài)自動(dòng)機(jī)有限狀態(tài)接收機(jī)（Acceptor）是一個(gè)五元組M=( Q, I, , q0, F ) 。是沒有輸出的有限狀態(tài)自動(dòng)機(jī)。有限狀態(tài)轉(zhuǎn)錄機(jī)（Transducer）是一個(gè)六元組M=( Q, I, U, , , q0) 。有輸出，但沒有終止?fàn)顟B(tài)的有限狀態(tài)自動(dòng)機(jī)。第33頁，共39頁。有限狀態(tài)自動(dòng)機(jī)的應(yīng)用有限狀態(tài)自動(dòng)機(jī)具有簡(jiǎn)單、直觀、高效的特點(diǎn)，在很多領(lǐng)域中得到了廣泛的應(yīng)用詞典構(gòu)造（Xerox Europe）機(jī)器翻譯（Alshiwiswork）有限狀態(tài)機(jī)自動(dòng)機(jī)通過遞歸（輸入另一個(gè)自動(dòng)機(jī)的識(shí)別結(jié)果）可以實(shí)現(xiàn)上下文無關(guān)語法的描述能力有限狀態(tài)轉(zhuǎn)

17、錄機(jī)可以進(jìn)行翻譯第34頁，共39頁。文法的判定復(fù)雜度PSG：半可判定對(duì)于一個(gè)屬于0型語言的句子L，總可以在確定步內(nèi)判斷出“是”；但對(duì)于一個(gè)不屬于0型語言的句子L，不存在一個(gè)算法，可以在確定步內(nèi)判斷出“否”。CSG：可判定，復(fù)雜度：NP完全CFG：可判定，復(fù)雜度：多項(xiàng)式RG：可判定，復(fù)雜度：線性第35頁，共39頁。文法、自動(dòng)機(jī)和語言文法自動(dòng)機(jī)語言復(fù)雜度0型無約束短語結(jié)構(gòu)文法圖靈機(jī)遞歸可枚舉語言 半可判定 1型上下文有關(guān)文法線性有界自動(dòng)機(jī) 上下文有關(guān)語言 NP完全 2型上下文無關(guān)文法下推自動(dòng)機(jī) 上下文無關(guān)語言 多項(xiàng)式 3型正則文法有限自動(dòng)機(jī) 正則語言 線形第36頁，共39頁。用什么文法描述自然語言正則語法描述能力太弱、上下文有關(guān)語法計(jì)算復(fù)雜度太高，上下文無關(guān)語法使用最為普遍從描述能力上說，上下文無關(guān)語法不足以描述自然語言自然語言中上下文相關(guān)的情況非常常見從計(jì)算復(fù)雜度來說，上下文無關(guān)語法的復(fù)雜度是多項(xiàng)式的，其復(fù)雜度可以忍受為彌補(bǔ)上下文無關(guān)語法描述能力的不足