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

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

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

3、接推導得到語言：L(G)= | VT*；S * 第6頁，共39頁。一個例子例：設形式文法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代表動詞短語等等。則句子“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頁。喬姆斯基的文法層級0型文法1型文法2型文法3型文法第8頁，共39頁。喬姆斯基0型文法短語結構文法，無限制重寫文法 PSG：Phrasal Structure Grammar對規(guī)則形式的約束對于規(guī)則形式?jīng)]有任何限制第9頁，共39頁。喬姆斯基1型文法上下文有關語法，上下文敏感語法CSG：Context Sensitive Grammar對規(guī)則形式的約束： ，是任意串，且的長度小于的長度 A A是非

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

6、ef|g|h+第13頁，共39頁。喬姆斯基層級以外的文法類別介于CFG和CSG之間的語法類別 索引文法（IG: Index Grammar） 可以生成anbncn形式的語言 樹粘接文法 TAG：Tree Adjoining Grammar與喬姆斯基語法層級相交叉的語法類別第14頁，共39頁。索引文法(1)索引文法是一個五元組（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)直接推導()的定義如果AX1X2Xk是規(guī)

7、則集中具有1)形式的規(guī)則，那么：A()X1(1) X2(2)Xk(k)其中，XiVN時，i；XiVT時，i如果AB(f)是規(guī)則集中具有2)形式的規(guī)則，那么A()B(f) 如果A(f)X1X2Xk是規(guī)則集中具有3)形式的規(guī)則，那么：A(f)X1(1) X2(2)Xk(k)其中，XiVN時，i；XiVT時，i推導(*)的定義和語言的定義與前面類似第16頁，共39頁。索引文法(3) 例子（規(guī)則集）S S()S ABCA() aAB() bBC() cCA aB bC c 推導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。蔣嚴&潘海華,1998。白碩,1998范疇文法的核心思想是把語言中的各種成分對應為某種“類型”/“范疇”，把語言結構的構造過程對應為“類型”/“范疇”之間的演算過程。http:/www.cs.man.ac.uk/ai/CG/第19頁，共39頁。范疇文法(2)：基本概念范疇文法里面有兩種基本范疇：S和N。粗略地

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

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

11、兩種：一種叫做“應用”(Application)，簡記為A；一種叫做“合成”(Composition)，簡記為C。應用就是完整的約分，即分母被約掉，只剩下分子作為結果；比如： S/N N S N NS S 合成就是約分后范疇表達式仍然帶著分母。比如： 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、。范疇演算的語言學假設假設了所有結構都是由詞匯負載的，這樣才能從詞匯的范疇標記推導出各個上級結構成分的范疇標記；假設了所有結合必定是鄰接成分的結合，而不可能有跨越鄰接成分的超距結合，這樣才能依托鄰接關系實現(xiàn)范疇標記的約分計算；假設了嚴格的語序關系，這樣才能從確定方向上找到約分的對象；假設了每個結構必須填項完備，這樣才能在最后獲得一個分母約干凈了的S標記。第25頁，共39頁。范疇文法存在的問題1 范疇標記和詞類不是一一對應的，要在具體的語流中確定具體詞的范疇標記有相當?shù)碾y度，甚至無異于先要理解。2 不負載在詞上面的結構（如漢語中的聯(lián)合結構、連謂結構等）就很難納入范疇語法的框架中去表達。3 超距相

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

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

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

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

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