跳至內容

樹-鄰接文法

維基百科,自由的百科全書

樹-鄰接文法(TAG)是 Aravind Joshi 定義的文法形式化。樹-鄰接(adjoining)文法在某種意義上類似於上下文無關文法,但是基本的重寫單位是樹而不是符號。上下文無關文法有把符號重寫為其他符號的規則,而樹-毗連文法有把樹的節點重寫為其他樹的規則。

文法規則

TAG 中的規則是帶有叫做「足節點」的特殊葉子的樹,它們錨接(anchor)到一個字。在 TAG 中有兩個種類的基本樹:「初始」樹(經常被表示為 '')和「輔助」樹('')。初始樹表示基本的價(valency)關係,而輔助樹允許遞歸[1] 輔助樹有標記(label)上同樣符號的根(頂)節點和足節點。推導開始於初始樹,通過要麼「代換」要麼「附加」來結合。代換把末梢節點替換為其頂節點有同樣符號的另一個樹。附加把一個輔助樹插入到另一個樹的中心。[2] 輔助樹的根/足標記必須匹配它所鄰接的節點的標記。其他 TAG 的變體允許多種成分的樹,帶有多個足節點的樹,和其他擴展。

樹-鄰接文法經常被描述為「適度上下文有關的」,這意味着它們有(在弱生成能力方面上)特定性質使其有比上下文無關文法更強力,但有比附標文法上下文有關文法更弱的能力。適度上下文有關文法被推測為足夠強力可以建模自然語言,而仍保持在一般情況下有效解析[3] 由於它們的形式特性,TAG 經常被用於計算語言學自然語言處理

文法緣起

TAG 起源於 Joshi 和他的學生對附加文法(AG)家族和 Zellig Harris 的「字符串文法」的研究 [4] 。AG 以自然和高效的方式處理語言的向心英語Endocentric and exocentric性質,但是沒有對離心構造的好特徵描述;重寫文法短語-結構文法(PSG)正好反過來。在 1969 年,Joshi 通過混合兩種類型的規則介入了開拓出這種補足的文法家族。一些非常簡單的重寫規則足夠生成附加規則的字符串的詞彙表。這個家族不同於喬姆斯基層級,但是有所交疊。[5]

TAG 可以描述有平方的語言(在其中某個任意字符串被重複),和語言 ,有立方的語言(就是三倍的字符串)或有相等長度的多於四個不同字符的字符串的語言不可以被樹-鄰接文法所生成。為此,樹-毗連文法生成的語言被稱為「適度上下文有關語言」。

引用

  1. ^ Jurafsky, Daniel; James H. Martin. Speech and Language Processing. Upper Saddle River, NJ: Prentice Hall. 2000: 354. 
  2. ^ Joshi, Aravind; Owen Rambow. A Formalism for Dependency Grammar Based on Tree Adjoining Grammar (PDF). Proceedings of the Conference on Meaning-Text Theory. 2003 [2007-10-19]. (原始內容存檔 (PDF)於2020-11-29). 
  3. ^ Joshi, Aravind. How much context-sensitivity is necessary for characterizing structural descriptions. D. Dowty, L. Karttunen, and A. Zwicky, (eds.) (編). Natural Language Processing: Theoretical, Computational, and Psychological Perspectives. New York, NY: Cambridge University Press. 1985: 206–250. 
  4. ^ Joshi, Aravind; S. R. Kosaraju, H. Yamada. String Adjunct Grammars. Proceedings Tenth Annual Symposium on Automata Theory, Waterloo, Canada. 1969. 
  5. ^ Joshi, Aravind. Properties of Formal Grammars with Mixed Types of Rules and Their Linguistic Relevance. Proceedings Third International Symposium on Computational Linguistics, Stockholm, Sweden. 1969. 

外部連結